code:
=================
Symbol Namespaces
=================

The following document describes how to use Symbol Namespaces to structure the
export surface of in-kernel symbols exported through the family of
EXPORT_SYMBOL() macros.

.. Table of Contents

	=== 1 Introduction
	=== 2 How to define Symbol Namespaces
	   --- 2.1 Using the EXPORT_SYMBOL macros
	   --- 2.2 Using the DEFAULT_SYMBOL_NAMESPACE define
	=== 3 How to use Symbols exported in Namespaces
	=== 4 Loading Modules that use namespaced Symbols
	=== 5 Automatically creating MODULE_IMPORT_NS statements

1. Introduction
===============

Symbol Namespaces have been introduced as a means to structure the export
surface of the in-kernel API. It allows subsystem maintainers to partition
their exported symbols into separate namespaces. That is useful for
documentation purposes (think of the SUBSYSTEM_DEBUG namespace) as well as for
limiting the availability of a set of symbols for use in other parts of the
kernel. As of today, modules that make use of symbols exported into namespaces,
are required to import the namespace. Otherwise the kernel will, depending on
its configuration, reject loading the module or warn about a missing import.

2. How to define Symbol Namespaces
==================================

Symbols can be exported into namespace using different methods. All of them are
changing the way EXPORT_SYMBOL and friends are instrumented to create ksymtab
entries.

2.1 Using the EXPORT_SYMBOL macros
==================================

In addition to the macros EXPORT_SYMBOL() and EXPORT_SYMBOL_GPL(), that allow
exporting of kernel symbols to the kernel symbol table, variants of these are
available to export symbols into a certain namespace: EXPORT_SYMBOL_NS() and
EXPORT_SYMBOL_NS_GPL(). They take one additional argument: the namespace.
Please note that due to macro expansion that argument needs to be a
preprocessor symbol. E.g. to export the symbol ``usb_stor_suspend`` into the
namespace ``USB_STORAGE``, use::

	EXPORT_SYMBOL_NS(usb_stor_suspend, USB_STORAGE);

The corresponding ksymtab entry struct ``kernel_symbol`` will have the member
``namespace`` set accordingly. A symbol that is exported without a namespace will
refer to ``NULL``. There is no default namespace if none is defined. ``modpost``
and kernel/module/main.c make use the namespace at build time or module load
time, respectively.

2.2 Using the DEFAULT_SYMBOL_NAMESPACE define
=============================================

Defining namespaces for all symbols of a subsystem can be very verbose and may
become hard to maintain. Therefore a default define (DEFAULT_SYMBOL_NAMESPACE)
is been provided, that, if set, will become the default for all EXPORT_SYMBOL()
and EXPORT_SYMBOL_GPL() macro expansions that do not specify a namespace.

There are multiple ways of specifying this define and it depends on the
subsystem and the maintainer's preference, which one to use. The first option
is to define the default namespace in the ``Makefile`` of the subsystem. E.g. to
export all symbols defined in usb-common into the namespace USB_COMMON, add a
line like this to drivers/usb/common/Makefile::

	ccflags-y += -DDEFAULT_SYMBOL_NAMESPACE=USB_COMMON

That will affect all EXPORT_SYMBOL() and EXPORT_SYMBOL_GPL() statements. A
symbol exported with EXPORT_SYMBOL_NS() while this definition is present, will
still be exported into the namespace that is passed as the namespace argument
as this argument has preference over a default symbol namespace.

A second option to define the default namespace is directly in the compilation
unit as preprocessor statement. The above example would then read::

	#undef  DEFAULT_SYMBOL_NAMESPACE
	#define DEFAULT_SYMBOL_NAMESPACE USB_COMMON

within the corresponding compilation unit before any EXPORT_SYMBOL macro is
used.

3. How to use Symbols exported in Namespaces
============================================

In order to use symbols that are exported into namespaces, kernel modules need
to explicitly import these namespaces. Otherwise the kernel might reject to
load the module. The module code is required to use the macro MODULE_IMPORT_NS
for the namespaces it uses symbols from. E.g. a module using the
usb_stor_suspend symbol from above, needs to import the namespace USB_STORAGE
using a statement like::

	MODULE_IMPORT_NS(USB_STORAGE);

This will create a ``modinfo`` tag in the module for each imported namespace.
This has the side effect, that the imported namespaces of a module can be
inspected with modinfo::

	$ modinfo drivers/usb/storage/ums-karma.ko
	[...]
	import_ns:      USB_STORAGE
	[...]

It is advisable to add the MODULE_IMPORT_NS() statement close to other module
metadata definitions like MODULE_AUTHOR() or MODULE_LICENSE(). Refer to section
5. for a way to create missing import statements automatically.

4. Loading Modules that use namespaced Symbols
==============================================

At module loading time (e.g. ``insmod``), the kernel will check each symbol
referenced from the module for its availability and whether the namespace it
might be exported to has been imported by the module. The default behaviour of
the kernel is to reject loading modules that don't specify sufficient imports.
An error will be logged and loading will be failed with EINVAL. In order to
allow loading of modules that don't satisfy this precondition, a configuration
option is available: Setting MODULE_ALLOW_MISSING_NAMESPACE_IMPORTS=y will
enable loading regardless, but will emit a warning.

5. Automatically creating MODULE_IMPORT_NS statements
=====================================================

Missing namespaces imports can easily be detected at build time. In fact,
modpost will emit a warning if a module uses a symbol from a namespace
without importing it.
MODULE_IMPORT_NS() statements will usually be added at a definite location
(along with other module meta data). To make the life of module authors (and
subsystem maintainers) easier, a script and make target is available to fixup
missing imports. Fixing missing imports can be done with::

	$ make nsdeps

A typical scenario for module authors would be::

	- write code that depends on a symbol from a not imported namespace
	- ``make``
	- notice the warning of modpost telling about a missing import
	- run ``make nsdeps`` to add the import to the correct code location

For subsystem maintainers introducing a namespace, the steps are very similar.
Again, ``make nsdeps`` will eventually add the missing namespace imports for
in-tree modules::

	- move or add symbols to a namespace (e.g. with EXPORT_SYMBOL_NS())
	- ``make`` (preferably with an allmodconfig to cover all in-kernel
	  modules)
	- notice the warning of modpost telling about a missing import
	- run ``make nsdeps`` to add the import to the correct code location

You can also run nsdeps for external module builds. A typical usage is::

	$ make -C <path_to_kernel_src> M=$PWD nsdeps


code:
===================
this_cpu operations
===================

:Author: Christoph Lameter, August 4th, 2014
:Author: Pranith Kumar, Aug 2nd, 2014

this_cpu operations are a way of optimizing access to per cpu
variables associated with the *currently* executing processor. This is
done through the use of segment registers (or a dedicated register where
the cpu permanently stored the beginning of the per cpu	area for a
specific processor).

this_cpu operations add a per cpu variable offset to the processor
specific per cpu base and encode that operation in the instruction
operating on the per cpu variable.

This means that there are no atomicity issues between the calculation of
the offset and the operation on the data. Therefore it is not
necessary to disable preemption or interrupts to ensure that the
processor is not changed between the calculation of the address and
the operation on the data.

Read-modify-write operations are of particular interest. Frequently
processors have special lower latency instructions that can operate
without the typical synchronization overhead, but still provide some
sort of relaxed atomicity guarantees. The x86, for example, can execute
RMW (Read Modify Write) instructions like inc/dec/cmpxchg without the
lock prefix and the associated latency penalty.

Access to the variable without the lock prefix is not synchronized but
synchronization is not necessary since we are dealing with per cpu
data specific to the currently executing processor. Only the current
processor should be accessing that variable and therefore there are no
concurrency issues with other processors in the system.

Please note that accesses by remote processors to a per cpu area are
exceptional situations and may impact performance and/or correctness
(remote write operations) of local RMW operations via this_cpu_*.

The main use of the this_cpu operations has been to optimize counter
operations.

The following this_cpu() operations with implied preemption protection
are defined. These operations can be used without worrying about
preemption and interrupts::

	this_cpu_read(pcp)
	this_cpu_write(pcp, val)
	this_cpu_add(pcp, val)
	this_cpu_and(pcp, val)
	this_cpu_or(pcp, val)
	this_cpu_add_return(pcp, val)
	this_cpu_xchg(pcp, nval)
	this_cpu_cmpxchg(pcp, oval, nval)
	this_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
	this_cpu_sub(pcp, val)
	this_cpu_inc(pcp)
	this_cpu_dec(pcp)
	this_cpu_sub_return(pcp, val)
	this_cpu_inc_return(pcp)
	this_cpu_dec_return(pcp)

Inner working of this_cpu operations
------------------------------------

On x86 the fs: or the gs: segment registers contain the base of the
per cpu area. It is then possible to simply use the segment override
to relocate a per cpu relative address to the proper per cpu area for
the processor. So the relocation to the per cpu base is encoded in the
instruction via a segment register prefix.

For example::

	DEFINE_PER_CPU(int, x);
	int z;

	z = this_cpu_read(x);

results in a single instruction::

	mov ax, gs:[x]

instead of a sequence of calculation of the address and then a fetch
from that address which occurs with the per cpu operations. Before
this_cpu_ops such sequence also required preempt disable/enable to
prevent the kernel from moving the thread to a different processor
while the calculation is performed.

Consider the following this_cpu operation::

	this_cpu_inc(x)

The above results in the following single instruction (no lock prefix!)::

	inc gs:[x]

instead of the following operations required if there is no segment
register::

	int *y;
	int cpu;

	cpu = get_cpu();
	y = per_cpu_ptr(&x, cpu);
	(*y)++;
	put_cpu();

Note that these operations can only be used on per cpu data that is
reserved for a specific processor. Without disabling preemption in the
surrounding code this_cpu_inc() will only guarantee that one of the
per cpu counters is correctly incremented. However, there is no
guarantee that the OS will not move the process directly before or
after the this_cpu instruction is executed. In general this means that
the value of the individual counters for each processor are
meaningless. The sum of all the per cpu counters is the only value
that is of interest.

Per cpu variables are used for performance reasons. Bouncing cache
lines can be avoided if multiple processors concurrently go through
the same code paths.  Since each processor has its own per cpu
variables no concurrent cache line updates take place. The price that
has to be paid for this optimization is the need to add up the per cpu
counters when the value of a counter is needed.

Special operations
------------------

::

	y = this_cpu_ptr(&x)

Takes the offset of a per cpu variable (&x !) and returns the address
of the per cpu variable that belongs to the currently executing
processor.  this_cpu_ptr avoids multiple steps that the common
get_cpu/put_cpu sequence requires. No processor number is
available. Instead, the offset of the local per cpu area is simply
added to the per cpu offset.

Note that this operation is usually used in a code segment when
preemption has been disabled. The pointer is then used to
access local per cpu data in a critical section. When preemption
is re-enabled this pointer is usually no longer useful since it may
no longer point to per cpu data of the current processor.

Per cpu variables and offsets
-----------------------------

Per cpu variables have *offsets* to the beginning of the per cpu
area. They do not have addresses although they look like that in the
code. Offsets cannot be directly dereferenced. The offset must be
added to a base pointer of a per cpu area of a processor in order to
form a valid address.

Therefore the use of x or &x outside of the context of per cpu
operations is invalid and will generally be treated like a NULL
pointer dereference.

::

	DEFINE_PER_CPU(int, x);

In the context of per cpu operations the above implies that x is a per
cpu variable. Most this_cpu operations take a cpu variable.

::

	int __percpu *p = &x;

&x and hence p is the *offset* of a per cpu variable. this_cpu_ptr()
takes the offset of a per cpu variable which makes this look a bit
strange.

Operations on a field of a per cpu structure
--------------------------------------------

Let's say we have a percpu structure::

	struct s {
		int n,m;
	};

	DEFINE_PER_CPU(struct s, p);

Operations on these fields are straightforward::

	this_cpu_inc(p.m)

	z = this_cpu_cmpxchg(p.m, 0, 1);

If we have an offset to struct s::

	struct s __percpu *ps = &p;

	this_cpu_dec(ps->m);

	z = this_cpu_inc_return(ps->n);

The calculation of the pointer may require the use of this_cpu_ptr()
if we do not make use of this_cpu ops later to manipulate fields::

	struct s *pp;

	pp = this_cpu_ptr(&p);

	pp->m--;

	z = pp->n++;

Variants of this_cpu ops
------------------------

this_cpu ops are interrupt safe. Some architectures do not support
these per cpu local operations. In that case the operation must be
replaced by code that disables interrupts, then does the operations
that are guaranteed to be atomic and then re-enable interrupts. Doing
so is expensive. If there are other reasons why the scheduler cannot
change the processor we are executing on then there is no reason to
disable interrupts. For that purpose the following __this_cpu operations
are provided.

These operations have no guarantee against concurrent interrupts or
preemption. If a per cpu variable is not used in an interrupt context
and the scheduler cannot preempt, then they are safe. If any interrupts
still occur while an operation is in progress and if the interrupt too
modifies the variable, then RMW actions can not be guaranteed to be
safe::

	__this_cpu_read(pcp)
	__this_cpu_write(pcp, val)
	__this_cpu_add(pcp, val)
	__this_cpu_and(pcp, val)
	__this_cpu_or(pcp, val)
	__this_cpu_add_return(pcp, val)
	__this_cpu_xchg(pcp, nval)
	__this_cpu_cmpxchg(pcp, oval, nval)
	__this_cpu_cmpxchg_double(pcp1, pcp2, oval1, oval2, nval1, nval2)
	__this_cpu_sub(pcp, val)
	__this_cpu_inc(pcp)
	__this_cpu_dec(pcp)
	__this_cpu_sub_return(pcp, val)
	__this_cpu_inc_return(pcp)
	__this_cpu_dec_return(pcp)

Will increment x and will not fall-back to code that disables
interrupts on platforms that cannot accomplish atomicity through
address relocation and a Read-Modify-Write operation in the same
instruction.

&this_cpu_ptr(pp)->n vs this_cpu_ptr(&pp->n)
--------------------------------------------

The first operation takes the offset and forms an address and then
adds the offset of the n field. This may result in two add
instructions emitted by the compiler.

The second one first adds the two offsets and then does the
relocation.  IMHO the second form looks cleaner and has an easier time
with (). The second form also is consistent with the way
this_cpu_read() and friends are used.

Remote access to per cpu data
------------------------------

Per cpu data structures are designed to be used by one cpu exclusively.
If you use the variables as intended, this_cpu_ops() are guaranteed to
be "atomic" as no other CPU has access to these data structures.

There are special cases where you might need to access per cpu data
structures remotely. It is usually safe to do a remote read access
and that is frequently done to summarize counters. Remote write access
something which could be problematic because this_cpu ops do not
have lock semantics. A remote write may interfere with a this_cpu
RMW operation.

Remote write accesses to percpu data structures are highly discouraged
unless absolutely necessary. Please consider using an IPI to wake up
the remote CPU and perform the update to its per cpu area.

To access per-cpu data structure remotely, typically the per_cpu_ptr()
function is used::

	DEFINE_PER_CPU(struct data, datap);

	struct data *p = per_cpu_ptr(&datap, cpu);

This makes it explicit that we are getting ready to access a percpu
area remotely.

You can also do the following to convert the datap offset to an address::

	struct data *p = this_cpu_ptr(&datap);

but, passing of pointers calculated via this_cpu_ptr to other cpus is
unusual and should be avoided.

Remote access are typically only for reading the status of another cpus
per cpu data. Write accesses can cause unique problems due to the
relaxed synchronization requirements for this_cpu operations.

One example that illustrates some concerns with write operations is
the following scenario that occurs because two per cpu variables
share a cache-line but the relaxed synchronization is applied to
only one process updating the cache-line.

Consider the following example::

	struct test {
		atomic_t a;
		int b;
	};

	DEFINE_PER_CPU(struct test, onecacheline);

There is some concern about what would happen if the field 'a' is updated
remotely from one processor and the local processor would use this_cpu ops
to update field b. Care should be taken that such simultaneous accesses to
data within the same cache line are avoided. Also costly synchronization
may be necessary. IPIs are generally recommended in such scenarios instead
of a remote write to the per cpu area of another processor.

Even in cases where the remote writes are rare, please bear in
mind that a remote write will evict the cache line from the processor
that most likely will access it. If the processor wakes up and finds a
missing local cache line of a per cpu area, its performance and hence
the wake up times will be affected.

repo_name: angery/linux


code:
ktime accessors
===============

Device drivers can read the current time using ktime_get() and the many
related functions declared in linux/timekeeping.h. As a rule of thumb,
using an accessor with a shorter name is preferred over one with a longer
name if both are equally fit for a particular use case.

Basic ktime_t based interfaces
------------------------------

The recommended simplest form returns an opaque ktime_t, with variants
that return time for different clock references:

.. c:function:: ktime_t ktime_get( void )

	CLOCK_MONOTONIC

	Useful for reliable timestamps and measuring short time intervals
	accurately. Starts at system boot time but stops during suspend.

.. c:function:: ktime_t ktime_get_boottime( void )

	CLOCK_BOOTTIME

	Like ktime_get(), but does not stop when suspended. This can be
	used e.g. for key expiration times that need to be synchronized
	with other machines across a suspend operation.

.. c:function:: ktime_t ktime_get_real( void )

	CLOCK_REALTIME

	Returns the time in relative to the UNIX epoch starting in 1970
	using the Coordinated Universal Time (UTC), same as gettimeofday()
	user space. This is used for all timestamps that need to
	persist across a reboot, like inode times, but should be avoided
	for internal uses, since it can jump backwards due to a leap
	second update, NTP adjustment settimeofday() operation from user
	space.

.. c:function:: ktime_t ktime_get_clocktai( void )

	 CLOCK_TAI

	Like ktime_get_real(), but uses the International Atomic Time (TAI)
	reference instead of UTC to avoid jumping on leap second updates.
	This is rarely useful in the kernel.

.. c:function:: ktime_t ktime_get_raw( void )

	CLOCK_MONOTONIC_RAW

	Like ktime_get(), but runs at the same rate as the hardware
	clocksource without (NTP) adjustments for clock drift. This is
	also rarely needed in the kernel.

nanosecond, timespec64, and second output
-----------------------------------------

For all of the above, there are variants that return the time in a
different format depending on what is required by the user:

.. c:function:: u64 ktime_get_ns( void )
		u64 ktime_get_boottime_ns( void )
		u64 ktime_get_real_ns( void )
		u64 ktime_get_clocktai_ns( void )
		u64 ktime_get_raw_ns( void )

	Same as the plain ktime_get functions, but returning a u64 number
	of nanoseconds in the respective time reference, which may be
	more convenient for some callers.

.. c:function:: void ktime_get_ts64( struct timespec64 * )
		void ktime_get_boottime_ts64( struct timespec64 * )
		void ktime_get_real_ts64( struct timespec64 * )
		void ktime_get_clocktai_ts64( struct timespec64 * )
		void ktime_get_raw_ts64( struct timespec64 * )

	Same above, but returns the time in a 'struct timespec64', split
	into seconds and nanoseconds. This can avoid an extra division
	when printing the time, or when passing it into an external
	interface that expects a 'timespec' or 'timeval' structure.

.. c:function:: time64_t ktime_get_seconds( void )
		time64_t ktime_get_boottime_seconds( void )
		time64_t ktime_get_real_seconds( void )
		time64_t ktime_get_clocktai_seconds( void )
		time64_t ktime_get_raw_seconds( void )

	Return a coarse-grained version of the time as a scalar
	time64_t. This avoids accessing the clock hardware and rounds
	down the seconds to the full seconds of the last timer tick
	using the respective reference.

Coarse and fast_ns access
-------------------------

Some additional variants exist for more specialized cases:

.. c:function:: ktime_t ktime_get_coarse( void )
		ktime_t ktime_get_coarse_boottime( void )
		ktime_t ktime_get_coarse_real( void )
		ktime_t ktime_get_coarse_clocktai( void )

.. c:function:: u64 ktime_get_coarse_ns( void )
		u64 ktime_get_coarse_boottime_ns( void )
		u64 ktime_get_coarse_real_ns( void )
		u64 ktime_get_coarse_clocktai_ns( void )

.. c:function:: void ktime_get_coarse_ts64( struct timespec64 * )
		void ktime_get_coarse_boottime_ts64( struct timespec64 * )
		void ktime_get_coarse_real_ts64( struct timespec64 * )
		void ktime_get_coarse_clocktai_ts64( struct timespec64 * )

	These are quicker than the non-coarse versions, but less accurate,
	corresponding to CLOCK_MONOTONIC_COARSE and CLOCK_REALTIME_COARSE
	in user space, along with the equivalent boottime/tai/raw
	timebase not available in user space.

	The time returned here corresponds to the last timer tick, which
	may be as much as 10ms in the past (for CONFIG_HZ=100), same as
	reading the 'jiffies' variable.  These are only useful when called
	in a fast path and one still expects better than second accuracy,
	but can't easily use 'jiffies', e.g. for inode timestamps.
	Skipping the hardware clock access saves around 100 CPU cycles
	on most modern machines with a reliable cycle counter, but
	up to several microseconds on older hardware with an external
	clocksource.

.. c:function:: u64 ktime_get_mono_fast_ns( void )
		u64 ktime_get_raw_fast_ns( void )
		u64 ktime_get_boot_fast_ns( void )
		u64 ktime_get_tai_fast_ns( void )
		u64 ktime_get_real_fast_ns( void )

	These variants are safe to call from any context, including from
	a non-maskable interrupt (NMI) during a timekeeper update, and
	while we are entering suspend with the clocksource powered down.
	This is useful in some tracing or debugging code as well as
	machine check reporting, but most drivers should never call them,
	since the time is allowed to jump under certain conditions.

Deprecated time interfaces
--------------------------

Older kernels used some other interfaces that are now being phased out
but may appear in third-party drivers being ported here. In particular,
all interfaces returning a 'struct timeval' or 'struct timespec' have
been replaced because the tv_sec member overflows in year 2038 on 32-bit
architectures. These are the recommended replacements:

.. c:function:: void ktime_get_ts( struct timespec * )

	Use ktime_get() or ktime_get_ts64() instead.

.. c:function:: void do_gettimeofday( struct timeval * )
		void getnstimeofday( struct timespec * )
		void getnstimeofday64( struct timespec64 * )
		void ktime_get_real_ts( struct timespec * )

	ktime_get_real_ts64() is a direct replacement, but consider using
	monotonic time (ktime_get_ts64()) and/or a ktime_t based interface
	(ktime_get()/ktime_get_real()).

.. c:function:: struct timespec current_kernel_time( void )
		struct timespec64 current_kernel_time64( void )
		struct timespec get_monotonic_coarse( void )
		struct timespec64 get_monotonic_coarse64( void )

	These are replaced by ktime_get_coarse_real_ts64() and
	ktime_get_coarse_ts64(). However, A lot of code that wants
	coarse-grained times can use the simple 'jiffies' instead, while
	some drivers may actually want the higher resolution accessors
	these days.

.. c:function:: struct timespec getrawmonotonic( void )
		struct timespec64 getrawmonotonic64( void )
		struct timespec timekeeping_clocktai( void )
		struct timespec64 timekeeping_clocktai64( void )
		struct timespec get_monotonic_boottime( void )
		struct timespec64 get_monotonic_boottime64( void )

	These are replaced by ktime_get_raw()/ktime_get_raw_ts64(),
	ktime_get_clocktai()/ktime_get_clocktai_ts64() as well
	as ktime_get_boottime()/ktime_get_boottime_ts64().
	However, if the particular choice of clock source is not
	important for the user, consider converting to
	ktime_get()/ktime_get_ts64() instead for consistency.


code:
===============================
The Linux Kernel Tracepoint API
===============================

:Author: Jason Baron
:Author: William Cohen

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

Tracepoints are static probe points that are located in strategic points
throughout the kernel. 'Probes' register/unregister with tracepoints via
a callback mechanism. The 'probes' are strictly typed functions that are
passed a unique set of parameters defined by each tracepoint.

From this simple callback mechanism, 'probes' can be used to profile,
debug, and understand kernel behavior. There are a number of tools that
provide a framework for using 'probes'. These tools include Systemtap,
ftrace, and LTTng.

Tracepoints are defined in a number of header files via various macros.
Thus, the purpose of this document is to provide a clear accounting of
the available tracepoints. The intention is to understand not only what
tracepoints are available but also to understand where future
tracepoints might be added.

The API presented has functions of the form:
``trace_tracepointname(function parameters)``. These are the tracepoints
callbacks that are found throughout the code. Registering and
unregistering probes with these callback sites is covered in the
``Documentation/trace/*`` directory.

IRQ
===

.. kernel-doc:: include/trace/events/irq.h
   :internal:

SIGNAL
======

.. kernel-doc:: include/trace/events/signal.h
   :internal:

Block IO
========

.. kernel-doc:: include/trace/events/block.h
   :internal:

Workqueue
=========

.. kernel-doc:: include/trace/events/workqueue.h
   :internal:


code:
=========================
Unaligned Memory Accesses
=========================

:Author: Daniel Drake <dsd@gentoo.org>,
:Author: Johannes Berg <johannes@sipsolutions.net>

:With help from: Alan Cox, Avuton Olrich, Heikki Orsila, Jan Engelhardt,
  Kyle McMartin, Kyle Moffett, Randy Dunlap, Robert Hancock, Uli Kunitz,
  Vadim Lobanov

Linux runs on a wide variety of architectures which have varying behaviour
when it comes to memory access. This document presents some details about
unaligned accesses, why you need to write code that doesn't cause them,
and how to write such code!

The definition of an unaligned access
=====================================

Unaligned memory accesses occur when you try to read N bytes of data starting
from an address that is not evenly divisible by N (i.e. addr % N != 0).
For example, reading 4 bytes of data from address 0x10004 is fine, but
reading 4 bytes of data from address 0x10005 would be an unaligned memory
access.

The above may seem a little vague, as memory access can happen in different
ways. The context here is at the machine code level: certain instructions read
or write a number of bytes to or from memory (e.g. movb, movw, movl in x86
assembly). As will become clear, it is relatively easy to spot C statements
which will compile to multiple-byte memory access instructions, namely when
dealing with types such as u16, u32 and u64.

Natural alignment
=================

The rule mentioned above forms what we refer to as natural alignment:
When accessing N bytes of memory, the base memory address must be evenly
divisible by N, i.e. addr % N == 0.

When writing code, assume the target architecture has natural alignment
requirements.

In reality, only a few architectures require natural alignment on all sizes
of memory access. However, we must consider ALL supported architectures;
writing code that satisfies natural alignment requirements is the easiest way
to achieve full portability.

Why unaligned access is bad
===========================

The effects of performing an unaligned memory access vary from architecture
to architecture. It would be easy to write a whole document on the differences
here; a summary of the common scenarios is presented below:

 - Some architectures are able to perform unaligned memory accesses
   transparently, but there is usually a significant performance cost.
 - Some architectures raise processor exceptions when unaligned accesses
   happen. The exception handler is able to correct the unaligned access,
   at significant cost to performance.
 - Some architectures raise processor exceptions when unaligned accesses
   happen, but the exceptions do not contain enough information for the
   unaligned access to be corrected.
 - Some architectures are not capable of unaligned memory access, but will
   silently perform a different memory access to the one that was requested,
   resulting in a subtle code bug that is hard to detect!

It should be obvious from the above that if your code causes unaligned
memory accesses to happen, your code will not work correctly on certain
platforms and will cause performance problems on others.

Code that does not cause unaligned access
=========================================

At first, the concepts above may seem a little hard to relate to actual
coding practice. After all, you don't have a great deal of control over
memory addresses of certain variables, etc.

Fortunately things are not too complex, as in most cases, the compiler
ensures that things will work for you. For example, take the following
structure::

	struct foo {
		u16 field1;
		u32 field2;
		u8 field3;
	};

Let us assume that an instance of the above structure resides in memory
starting at address 0x10000. With a basic level of understanding, it would
not be unreasonable to expect that accessing field2 would cause an unaligned
access. You'd be expecting field2 to be located at offset 2 bytes into the
structure, i.e. address 0x10002, but that address is not evenly divisible
by 4 (remember, we're reading a 4 byte value here).

Fortunately, the compiler understands the alignment constraints, so in the
above case it would insert 2 bytes of padding in between field1 and field2.
Therefore, for standard structure types you can always rely on the compiler
to pad structures so that accesses to fields are suitably aligned (assuming
you do not cast the field to a type of different length).

Similarly, you can also rely on the compiler to align variables and function
parameters to a naturally aligned scheme, based on the size of the type of
the variable.

At this point, it should be clear that accessing a single byte (u8 or char)
will never cause an unaligned access, because all memory addresses are evenly
divisible by one.

On a related topic, with the above considerations in mind you may observe
that you could reorder the fields in the structure in order to place fields
where padding would otherwise be inserted, and hence reduce the overall
resident memory size of structure instances. The optimal layout of the
above example is::

	struct foo {
		u32 field2;
		u16 field1;
		u8 field3;
	};

For a natural alignment scheme, the compiler would only have to add a single
byte of padding at the end of the structure. This padding is added in order
to satisfy alignment constraints for arrays of these structures.

Another point worth mentioning is the use of __attribute__((packed)) on a
structure type. This GCC-specific attribute tells the compiler never to
insert any padding within structures, useful when you want to use a C struct
to represent some data that comes in a fixed arrangement 'off the wire'.

You might be inclined to believe that usage of this attribute can easily
lead to unaligned accesses when accessing fields that do not satisfy
architectural alignment requirements. However, again, the compiler is aware
of the alignment constraints and will generate extra instructions to perform
the memory access in a way that does not cause unaligned access. Of course,
the extra instructions obviously cause a loss in performance compared to the
non-packed case, so the packed attribute should only be used when avoiding
structure padding is of importance.

Code that causes unaligned access
=================================

With the above in mind, let's move onto a real life example of a function
that can cause an unaligned memory access. The following function taken
from include/linux/etherdevice.h is an optimized routine to compare two
ethernet MAC addresses for equality::

  bool ether_addr_equal(const u8 *addr1, const u8 *addr2)
  {
  #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
	u32 fold = ((*(const u32 *)addr1) ^ (*(const u32 *)addr2)) |
		   ((*(const u16 *)(addr1 + 4)) ^ (*(const u16 *)(addr2 + 4)));

	return fold == 0;
  #else
	const u16 *a = (const u16 *)addr1;
	const u16 *b = (const u16 *)addr2;
	return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2])) == 0;
  #endif
  }

In the above function, when the hardware has efficient unaligned access
capability, there is no issue with this code.  But when the hardware isn't
able to access memory on arbitrary boundaries, the reference to a[0] causes
2 bytes (16 bits) to be read from memory starting at address addr1.

Think about what would happen if addr1 was an odd address such as 0x10003.
(Hint: it'd be an unaligned access.)

Despite the potential unaligned access problems with the above function, it
is included in the kernel anyway but is understood to only work normally on
16-bit-aligned addresses. It is up to the caller to ensure this alignment or
not use this function at all. This alignment-unsafe function is still useful
as it is a decent optimization for the cases when you can ensure alignment,
which is true almost all of the time in ethernet networking context.

Here is another example of some code that could cause unaligned accesses::

	void myfunc(u8 *data, u32 value)
	{
		[...]
		*((u32 *) data) = cpu_to_le32(value);
		[...]
	}

This code will cause unaligned accesses every time the data parameter points
to an address that is not evenly divisible by 4.

In summary, the 2 main scenarios where you may run into unaligned access
problems involve:

 1. Casting variables to types of different lengths
 2. Pointer arithmetic followed by access to at least 2 bytes of data

Avoiding unaligned accesses
===========================

The easiest way to avoid unaligned access is to use the get_unaligned() and
put_unaligned() macros provided by the <asm/unaligned.h> header file.

Going back to an earlier example of code that potentially causes unaligned
access::

	void myfunc(u8 *data, u32 value)
	{
		[...]
		*((u32 *) data) = cpu_to_le32(value);
		[...]
	}

To avoid the unaligned memory access, you would rewrite it as follows::

	void myfunc(u8 *data, u32 value)
	{
		[...]
		value = cpu_to_le32(value);
		put_unaligned(value, (u32 *) data);
		[...]
	}

The get_unaligned() macro works similarly. Assuming 'data' is a pointer to
memory and you wish to avoid unaligned access, its usage is as follows::

	u32 value = get_unaligned((u32 *) data);

These macros work for memory accesses of any length (not just 32 bits as
in the examples above). Be aware that when compared to standard access of
aligned memory, using these macros to access unaligned memory can be costly in
terms of performance.

If use of such macros is not convenient, another option is to use memcpy(),
where the source or destination (or both) are of type u8* or unsigned char*.
Due to the byte-wise nature of this operation, unaligned accesses are avoided.

Alignment vs. Networking
========================

On architectures that require aligned loads, networking requires that the IP
header is aligned on a four-byte boundary to optimise the IP stack. For
regular ethernet hardware, the constant NET_IP_ALIGN is used. On most
architectures this constant has the value 2 because the normal ethernet
header is 14 bytes long, so in order to get proper alignment one needs to
DMA to an address which can be expressed as 4*n + 2. One notable exception
here is powerpc which defines NET_IP_ALIGN to 0 because DMA to unaligned
addresses can be very expensive and dwarf the cost of unaligned loads.

For some ethernet hardware that cannot DMA to unaligned addresses like
4*n+2 or non-ethernet hardware, this can be a problem, and it is then
required to copy the incoming frame into an aligned buffer. Because this is
unnecessary on architectures that can do unaligned accesses, the code can be
made dependent on CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS like so::

	#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
		skb = original skb
	#else
		skb = copy skb
	#endif


code:
==============================
General notification mechanism
==============================

The general notification mechanism is built on top of the standard pipe driver
whereby it effectively splices notification messages from the kernel into pipes
opened by userspace.  This can be used in conjunction with::

  * Key/keyring notifications

The notifications buffers can be enabled by:

	"General setup"/"General notification queue"
	(CONFIG_WATCH_QUEUE)

This document has the following sections:

.. contents:: :local:

Overview
========

This facility appears as a pipe that is opened in a special mode.  The pipe's
internal ring buffer is used to hold messages that are generated by the kernel.
These messages are then read out by read().  Splice and similar are disabled on
such pipes due to them wanting to, under some circumstances, revert their
additions to the ring - which might end up interleaved with notification
messages.

The owner of the pipe has to tell the kernel which sources it would like to
watch through that pipe.  Only sources that have been connected to a pipe will
insert messages into it.  Note that a source may be bound to multiple pipes and
insert messages into all of them simultaneously.

Filters may also be emplaced on a pipe so that certain source types and
subevents can be ignored if they're not of interest.

A message will be discarded if there isn't a slot available in the ring or if
no preallocated message buffer is available.  In both of these cases, read()
will insert a WATCH_META_LOSS_NOTIFICATION message into the output buffer after
the last message currently in the buffer has been read.

Note that when producing a notification, the kernel does not wait for the
consumers to collect it, but rather just continues on.  This means that
notifications can be generated whilst spinlocks are held and also protects the
kernel from being held up indefinitely by a userspace malfunction.

Message Structure
=================

Notification messages begin with a short header::

	struct watch_notification {
		__u32	type:24;
		__u32	subtype:8;
		__u32	info;
	};

"type" indicates the source of the notification record and "subtype" indicates
the type of record from that source (see the Watch Sources section below).  The
type may also be "WATCH_TYPE_META".  This is a special record type generated
internally by the watch queue itself.  There are two subtypes:

  * WATCH_META_REMOVAL_NOTIFICATION
  * WATCH_META_LOSS_NOTIFICATION

The first indicates that an object on which a watch was installed was removed
or destroyed and the second indicates that some messages have been lost.

"info" indicates a bunch of things, including:

  * The length of the message in bytes, including the header (mask with
    WATCH_INFO_LENGTH and shift by WATCH_INFO_LENGTH__SHIFT).  This indicates
    the size of the record, which may be between 8 and 127 bytes.

  * The watch ID (mask with WATCH_INFO_ID and shift by WATCH_INFO_ID__SHIFT).
    This indicates that caller's ID of the watch, which may be between 0
    and 255.  Multiple watches may share a queue, and this provides a means to
    distinguish them.

  * A type-specific field (WATCH_INFO_TYPE_INFO).  This is set by the
    notification producer to indicate some meaning specific to the type and
    subtype.

Everything in info apart from the length can be used for filtering.

The header can be followed by supplementary information.  The format of this is
at the discretion is defined by the type and subtype.

Watch List (Notification Source) API
====================================

A "watch list" is a list of watchers that are subscribed to a source of
notifications.  A list may be attached to an object (say a key or a superblock)
or may be global (say for device events).  From a userspace perspective, a
non-global watch list is typically referred to by reference to the object it
belongs to (such as using KEYCTL_NOTIFY and giving it a key serial number to
watch that specific key).

To manage a watch list, the following functions are provided:

  * ::

	void init_watch_list(struct watch_list *wlist,
			     void (*release_watch)(struct watch *wlist));

    Initialise a watch list.  If ``release_watch`` is not NULL, then this
    indicates a function that should be called when the watch_list object is
    destroyed to discard any references the watch list holds on the watched
    object.

  * ``void remove_watch_list(struct watch_list *wlist);``

    This removes all of the watches subscribed to a watch_list and frees them
    and then destroys the watch_list object itself.

Watch Queue (Notification Output) API
=====================================

A "watch queue" is the buffer allocated by an application that notification
records will be written into.  The workings of this are hidden entirely inside
of the pipe device driver, but it is necessary to gain a reference to it to set
a watch.  These can be managed with:

  * ``struct watch_queue *get_watch_queue(int fd);``

    Since watch queues are indicated to the kernel by the fd of the pipe that
    implements the buffer, userspace must hand that fd through a system call.
    This can be used to look up an opaque pointer to the watch queue from the
    system call.

  * ``void put_watch_queue(struct watch_queue *wqueue);``

    This discards the reference obtained from ``get_watch_queue()``.

Watch Subscription API
======================

A "watch" is a subscription on a watch list, indicating the watch queue, and
thus the buffer, into which notification records should be written.  The watch
queue object may also carry filtering rules for that object, as set by
userspace.  Some parts of the watch struct can be set by the driver::

	struct watch {
		union {
			u32		info_id;	/* ID to be OR'd in to info field */
			...
		};
		void			*private;	/* Private data for the watched object */
		u64			id;		/* Internal identifier */
		...
	};

The ``info_id`` value should be an 8-bit number obtained from userspace and
shifted by WATCH_INFO_ID__SHIFT.  This is OR'd into the WATCH_INFO_ID field of
struct watch_notification::info when and if the notification is written into
the associated watch queue buffer.

The ``private`` field is the driver's data associated with the watch_list and
is cleaned up by the ``watch_list::release_watch()`` method.

The ``id`` field is the source's ID.  Notifications that are posted with a
different ID are ignored.

The following functions are provided to manage watches:

  * ``void init_watch(struct watch *watch, struct watch_queue *wqueue);``

    Initialise a watch object, setting its pointer to the watch queue, using
    appropriate barriering to avoid lockdep complaints.

  * ``int add_watch_to_object(struct watch *watch, struct watch_list *wlist);``

    Subscribe a watch to a watch list (notification source).  The
    driver-settable fields in the watch struct must have been set before this
    is called.

  * ::

	int remove_watch_from_object(struct watch_list *wlist,
				     struct watch_queue *wqueue,
				     u64 id, false);

    Remove a watch from a watch list, where the watch must match the specified
    watch queue (``wqueue``) and object identifier (``id``).  A notification
    (``WATCH_META_REMOVAL_NOTIFICATION``) is sent to the watch queue to
    indicate that the watch got removed.

  * ``int remove_watch_from_object(struct watch_list *wlist, NULL, 0, true);``

    Remove all the watches from a watch list.  It is expected that this will be
    called preparatory to destruction and that the watch list will be
    inaccessible to new watches by this point.  A notification
    (``WATCH_META_REMOVAL_NOTIFICATION``) is sent to the watch queue of each
    subscribed watch to indicate that the watch got removed.

Notification Posting API
========================

To post a notification to watch list so that the subscribed watches can see it,
the following function should be used::

	void post_watch_notification(struct watch_list *wlist,
				     struct watch_notification *n,
				     const struct cred *cred,
				     u64 id);

The notification should be preformatted and a pointer to the header (``n``)
should be passed in.  The notification may be larger than this and the size in
units of buffer slots is noted in ``n->info & WATCH_INFO_LENGTH``.

The ``cred`` struct indicates the credentials of the source (subject) and is
passed to the LSMs, such as SELinux, to allow or suppress the recording of the
note in each individual queue according to the credentials of that queue
(object).

The ``id`` is the ID of the source object (such as the serial number on a key).
Only watches that have the same ID set in them will see this notification.

Watch Sources
=============

Any particular buffer can be fed from multiple sources.  Sources include:

  * WATCH_TYPE_KEY_NOTIFY

    Notifications of this type indicate changes to keys and keyrings, including
    the changes of keyring contents or the attributes of keys.

    See Documentation/security/keys/core.rst for more information.

Event Filtering
===============

Once a watch queue has been created, a set of filters can be applied to limit
the events that are received using::

	struct watch_notification_filter filter = {
		...
	};
	ioctl(fd, IOC_WATCH_QUEUE_SET_FILTER, &filter)

The filter description is a variable of type::

	struct watch_notification_filter {
		__u32	nr_filters;
		__u32	__reserved;
		struct watch_notification_type_filter filters[];
	};

Where "nr_filters" is the number of filters in filters[] and "__reserved"
should be 0.  The "filters" array has elements of the following type::

	struct watch_notification_type_filter {
		__u32	type;
		__u32	info_filter;
		__u32	info_mask;
		__u32	subtype_filter[8];
	};

Where:

  * ``type`` is the event type to filter for and should be something like
    "WATCH_TYPE_KEY_NOTIFY"

  * ``info_filter`` and ``info_mask`` act as a filter on the info field of the
    notification record.  The notification is only written into the buffer if::

	(watch.info & info_mask) == info_filter

    This could be used, for example, to ignore events that are not exactly on
    the watched point in a mount tree.

  * ``subtype_filter`` is a bitmask indicating the subtypes that are of
    interest.  Bit 0 of subtype_filter[0] corresponds to subtype 0, bit 1 to
    subtype 1, and so on.

If the argument to the ioctl() is NULL, then the filters will be removed and
all events from the watched sources will come through.

Userspace Code Example
======================

A buffer is created with something like the following::

	pipe2(fds, O_TMPFILE);
	ioctl(fds[1], IOC_WATCH_QUEUE_SET_SIZE, 256);

It can then be set to receive keyring change notifications::

	keyctl(KEYCTL_WATCH_KEY, KEY_SPEC_SESSION_KEYRING, fds[1], 0x01);

The notifications can then be consumed by something like the following::

	static void consumer(int rfd, struct watch_queue_buffer *buf)
	{
		unsigned char buffer[128];
		ssize_t buf_len;

		while (buf_len = read(rfd, buffer, sizeof(buffer)),
		       buf_len > 0
		       ) {
			void *p = buffer;
			void *end = buffer + buf_len;
			while (p < end) {
				union {
					struct watch_notification n;
					unsigned char buf1[128];
				} n;
				size_t largest, len;

				largest = end - p;
				if (largest > 128)
					largest = 128;
				memcpy(&n, p, largest);

				len = (n->info & WATCH_INFO_LENGTH) >>
					WATCH_INFO_LENGTH__SHIFT;
				if (len == 0 || len > largest)
					return;

				switch (n.n.type) {
				case WATCH_TYPE_META:
					got_meta(&n.n);
				case WATCH_TYPE_KEY_NOTIFY:
					saw_key_change(&n.n);
					break;
				}

				p += len;
			}
		}
	}


code:
====================================
Concurrency Managed Workqueue (cmwq)
====================================

:Date: September, 2010
:Author: Tejun Heo <tj@kernel.org>
:Author: Florian Mickler <florian@mickler.org>

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

There are many cases where an asynchronous process execution context
is needed and the workqueue (wq) API is the most commonly used
mechanism for such cases.

When such an asynchronous execution context is needed, a work item
describing which function to execute is put on a queue.  An
independent thread serves as the asynchronous execution context.  The
queue is called workqueue and the thread is called worker.

While there are work items on the workqueue the worker executes the
functions associated with the work items one after the other.  When
there is no work item left on the workqueue the worker becomes idle.
When a new work item gets queued, the worker begins executing again.

Why cmwq?
=========

In the original wq implementation, a multi threaded (MT) wq had one
worker thread per CPU and a single threaded (ST) wq had one worker
thread system-wide.  A single MT wq needed to keep around the same
number of workers as the number of CPUs.  The kernel grew a lot of MT
wq users over the years and with the number of CPU cores continuously
rising, some systems saturated the default 32k PID space just booting
up.

Although MT wq wasted a lot of resource, the level of concurrency
provided was unsatisfactory.  The limitation was common to both ST and
MT wq albeit less severe on MT.  Each wq maintained its own separate
worker pool.  An MT wq could provide only one execution context per CPU
while an ST wq one for the whole system.  Work items had to compete for
those very limited execution contexts leading to various problems
including proneness to deadlocks around the single execution context.

The tension between the provided level of concurrency and resource
usage also forced its users to make unnecessary tradeoffs like libata
choosing to use ST wq for polling PIOs and accepting an unnecessary
limitation that no two polling PIOs can progress at the same time.  As
MT wq don't provide much better concurrency, users which require
higher level of concurrency, like async or fscache, had to implement
their own thread pool.

Concurrency Managed Workqueue (cmwq) is a reimplementation of wq with
focus on the following goals.

* Maintain compatibility with the original workqueue API.

* Use per-CPU unified worker pools shared by all wq to provide
  flexible level of concurrency on demand without wasting a lot of
  resource.

* Automatically regulate worker pool and level of concurrency so that
  the API users don't need to worry about such details.

The Design
==========

In order to ease the asynchronous execution of functions a new
abstraction, the work item, is introduced.

A work item is a simple struct that holds a pointer to the function
that is to be executed asynchronously.  Whenever a driver or subsystem
wants a function to be executed asynchronously it has to set up a work
item pointing to that function and queue that work item on a
workqueue.

Special purpose threads, called worker threads, execute the functions
off of the queue, one after the other.  If no work is queued, the
worker threads become idle.  These worker threads are managed in so
called worker-pools.

The cmwq design differentiates between the user-facing workqueues that
subsystems and drivers queue work items on and the backend mechanism
which manages worker-pools and processes the queued work items.

There are two worker-pools, one for normal work items and the other
for high priority ones, for each possible CPU and some extra
worker-pools to serve work items queued on unbound workqueues - the
number of these backing pools is dynamic.

Subsystems and drivers can create and queue work items through special
workqueue API functions as they see fit. They can influence some
aspects of the way the work items are executed by setting flags on the
workqueue they are putting the work item on. These flags include
things like CPU locality, concurrency limits, priority and more.  To
get a detailed overview refer to the API description of
``alloc_workqueue()`` below.

When a work item is queued to a workqueue, the target worker-pool is
determined according to the queue parameters and workqueue attributes
and appended on the shared worklist of the worker-pool.  For example,
unless specifically overridden, a work item of a bound workqueue will
be queued on the worklist of either normal or highpri worker-pool that
is associated to the CPU the issuer is running on.

For any worker pool implementation, managing the concurrency level
(how many execution contexts are active) is an important issue.  cmwq
tries to keep the concurrency at a minimal but sufficient level.
Minimal to save resources and sufficient in that the system is used at
its full capacity.

Each worker-pool bound to an actual CPU implements concurrency
management by hooking into the scheduler.  The worker-pool is notified
whenever an active worker wakes up or sleeps and keeps track of the
number of the currently runnable workers.  Generally, work items are
not expected to hog a CPU and consume many cycles.  That means
maintaining just enough concurrency to prevent work processing from
stalling should be optimal.  As long as there are one or more runnable
workers on the CPU, the worker-pool doesn't start execution of a new
work, but, when the last running worker goes to sleep, it immediately
schedules a new worker so that the CPU doesn't sit idle while there
are pending work items.  This allows using a minimal number of workers
without losing execution bandwidth.

Keeping idle workers around doesn't cost other than the memory space
for kthreads, so cmwq holds onto idle ones for a while before killing
them.

For unbound workqueues, the number of backing pools is dynamic.
Unbound workqueue can be assigned custom attributes using
``apply_workqueue_attrs()`` and workqueue will automatically create
backing worker pools matching the attributes.  The responsibility of
regulating concurrency level is on the users.  There is also a flag to
mark a bound wq to ignore the concurrency management.  Please refer to
the API section for details.

Forward progress guarantee relies on that workers can be created when
more execution contexts are necessary, which in turn is guaranteed
through the use of rescue workers.  All work items which might be used
on code paths that handle memory reclaim are required to be queued on
wq's that have a rescue-worker reserved for execution under memory
pressure.  Else it is possible that the worker-pool deadlocks waiting
for execution contexts to free up.

Application Programming Interface (API)
=======================================

``alloc_workqueue()`` allocates a wq.  The original
``create_*workqueue()`` functions are deprecated and scheduled for
removal.  ``alloc_workqueue()`` takes three arguments - ``@name``,
``@flags`` and ``@max_active``.  ``@name`` is the name of the wq and
also used as the name of the rescuer thread if there is one.

A wq no longer manages execution resources but serves as a domain for
forward progress guarantee, flush and work item attributes. ``@flags``
and ``@max_active`` control how work items are assigned execution
resources, scheduled and executed.

``flags``
---------

``WQ_UNBOUND``
  Work items queued to an unbound wq are served by the special
  worker-pools which host workers which are not bound to any
  specific CPU.  This makes the wq behave as a simple execution
  context provider without concurrency management.  The unbound
  worker-pools try to start execution of work items as soon as
  possible.  Unbound wq sacrifices locality but is useful for
  the following cases.

  * Wide fluctuation in the concurrency level requirement is
    expected and using bound wq may end up creating large number
    of mostly unused workers across different CPUs as the issuer
    hops through different CPUs.

  * Long running CPU intensive workloads which can be better
    managed by the system scheduler.

``WQ_FREEZABLE``
  A freezable wq participates in the freeze phase of the system
  suspend operations.  Work items on the wq are drained and no
  new work item starts execution until thawed.

``WQ_MEM_RECLAIM``
  All wq which might be used in the memory reclaim paths **MUST**
  have this flag set.  The wq is guaranteed to have at least one
  execution context regardless of memory pressure.

``WQ_HIGHPRI``
  Work items of a highpri wq are queued to the highpri
  worker-pool of the target cpu.  Highpri worker-pools are
  served by worker threads with elevated nice level.

  Note that normal and highpri worker-pools don't interact with
  each other.  Each maintains its separate pool of workers and
  implements concurrency management among its workers.

``WQ_CPU_INTENSIVE``
  Work items of a CPU intensive wq do not contribute to the
  concurrency level.  In other words, runnable CPU intensive
  work items will not prevent other work items in the same
  worker-pool from starting execution.  This is useful for bound
  work items which are expected to hog CPU cycles so that their
  execution is regulated by the system scheduler.

  Although CPU intensive work items don't contribute to the
  concurrency level, start of their executions is still
  regulated by the concurrency management and runnable
  non-CPU-intensive work items can delay execution of CPU
  intensive work items.

  This flag is meaningless for unbound wq.

``max_active``
--------------

``@max_active`` determines the maximum number of execution contexts
per CPU which can be assigned to the work items of a wq.  For example,
with ``@max_active`` of 16, at most 16 work items of the wq can be
executing at the same time per CPU.

Currently, for a bound wq, the maximum limit for ``@max_active`` is
512 and the default value used when 0 is specified is 256.  For an
unbound wq, the limit is higher of 512 and 4 *
``num_possible_cpus()``.  These values are chosen sufficiently high
such that they are not the limiting factor while providing protection
in runaway cases.

The number of active work items of a wq is usually regulated by the
users of the wq, more specifically, by how many work items the users
may queue at the same time.  Unless there is a specific need for
throttling the number of active work items, specifying '0' is
recommended.

Some users depend on the strict execution ordering of ST wq.  The
combination of ``@max_active`` of 1 and ``WQ_UNBOUND`` used to
achieve this behavior.  Work items on such wq were always queued to the
unbound worker-pools and only one work item could be active at any given
time thus achieving the same ordering property as ST wq.

In the current implementation the above configuration only guarantees
ST behavior within a given NUMA node. Instead ``alloc_ordered_queue()`` should
be used to achieve system-wide ST behavior.

Example Execution Scenarios
===========================

The following example execution scenarios try to illustrate how cmwq
behave under different configurations.

 Work items w0, w1, w2 are queued to a bound wq q0 on the same CPU.
 w0 burns CPU for 5ms then sleeps for 10ms then burns CPU for 5ms
 again before finishing.  w1 and w2 burn CPU for 5ms then sleep for
 10ms.

Ignoring all other tasks, works and processing overhead, and assuming
simple FIFO scheduling, the following is one highly simplified version
of possible sequences of events with the original wq. ::

 TIME IN MSECS	EVENT
 0		w0 starts and burns CPU
 5		w0 sleeps
 15		w0 wakes up and burns CPU
 20		w0 finishes
 20		w1 starts and burns CPU
 25		w1 sleeps
 35		w1 wakes up and finishes
 35		w2 starts and burns CPU
 40		w2 sleeps
 50		w2 wakes up and finishes

And with cmwq with ``@max_active`` >= 3, ::

 TIME IN MSECS	EVENT
 0		w0 starts and burns CPU
 5		w0 sleeps
 5		w1 starts and burns CPU
 10		w1 sleeps
 10		w2 starts and burns CPU
 15		w2 sleeps
 15		w0 wakes up and burns CPU
 20		w0 finishes
 20		w1 wakes up and finishes
 25		w2 wakes up and finishes

If ``@max_active`` == 2, ::

 TIME IN MSECS	EVENT
 0		w0 starts and burns CPU
 5		w0 sleeps
 5		w1 starts and burns CPU
 10		w1 sleeps
 15		w0 wakes up and burns CPU
 20		w0 finishes
 20		w1 wakes up and finishes
 20		w2 starts and burns CPU
 25		w2 sleeps
 35		w2 wakes up and finishes

Now, let's assume w1 and w2 are queued to a different wq q1 which has
``WQ_CPU_INTENSIVE`` set, ::

 TIME IN MSECS	EVENT
 0		w0 starts and burns CPU
 5		w0 sleeps
 5		w1 and w2 start and burn CPU
 10		w1 sleeps
 15		w2 sleeps
 15		w0 wakes up and burns CPU
 20		w0 finishes
 20		w1 wakes up and finishes
 25		w2 wakes up and finishes

Guidelines
==========

* Do not forget to use ``WQ_MEM_RECLAIM`` if a wq may process work
  items which are used during memory reclaim.  Each wq with
  ``WQ_MEM_RECLAIM`` set has an execution context reserved for it.  If
  there is dependency among multiple work items used during memory
  reclaim, they should be queued to separate wq each with
  ``WQ_MEM_RECLAIM``.

* Unless strict ordering is required, there is no need to use ST wq.

* Unless there is a specific need, using 0 for @max_active is
  recommended.  In most use cases, concurrency level usually stays
  well under the default limit.

* A wq serves as a domain for forward progress guarantee
  (``WQ_MEM_RECLAIM``, flush and work item attributes.  Work items
  which are not involved in memory reclaim and don't need to be
  flushed as a part of a group of work items, and don't require any
  special attribute, can use one of the system wq.  There is no
  difference in execution characteristics between using a dedicated wq
  and a system wq.

* Unless work items are expected to consume a huge amount of CPU
  cycles, using a bound wq is usually beneficial due to the increased
  level of locality in wq operations and work item execution.

Debugging
=========

Because the work functions are executed by generic worker threads
there are a few tricks needed to shed some light on misbehaving
workqueue users.

Worker threads show up in the process list as: ::

  root      5671  0.0  0.0      0     0 ?        S    12:07   0:00 [kworker/0:1]
  root      5672  0.0  0.0      0     0 ?        S    12:07   0:00 [kworker/1:2]
  root      5673  0.0  0.0      0     0 ?        S    12:12   0:00 [kworker/0:0]
  root      5674  0.0  0.0      0     0 ?        S    12:13   0:00 [kworker/1:0]

If kworkers are going crazy (using too much cpu), there are two types
of possible problems:

	1. Something being scheduled in rapid succession
	2. A single work item that consumes lots of cpu cycles

The first one can be tracked using tracing: ::

	$ echo workqueue:workqueue_queue_work > /sys/kernel/debug/tracing/set_event
	$ cat /sys/kernel/debug/tracing/trace_pipe > out.txt
	(wait a few secs)
	^C

If something is busy looping on work queueing, it would be dominating
the output and the offender can be determined with the work item
function.

For the second type of problems it should be possible to just check
the stack trace of the offending worker thread. ::

	$ cat /proc/THE_OFFENDING_KWORKER/stack

The work item's function should be trivially visible in the stack
trace.

Non-reentrance Conditions
=========================

Workqueue guarantees that a work item cannot be re-entrant if the following
conditions hold after a work item gets queued:

        1. The work function hasn't been changed.
        2. No one queues the work item to another workqueue.
        3. The work item hasn't been reinitiated.

In other words, if the above conditions hold, the work item is guaranteed to be
executed by at most one worker system-wide at any given time.

Note that requeuing the work item (to the same queue) in the self function
doesn't break these conditions, so it's safe to do. Otherwise, caution is
required when breaking the conditions inside a work function.

Kernel Inline Documentations Reference
======================================

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

.. kernel-doc:: kernel/workqueue.c


code:
.. SPDX-License-Identifier: GPL-2.0
   This is a simple wrapper to bring atomic_bitops.txt into the RST world
   until such a time as that file can be converted directly.

=============
Atomic bitops
=============

.. raw:: latex

    \footnotesize

.. include:: ../../atomic_bitops.txt
   :literal:

.. raw:: latex

    \normalsize


code:
.. SPDX-License-Identifier: GPL-2.0
   This is a simple wrapper to bring atomic_t.txt into the RST world
   until such a time as that file can be converted directly.

============
Atomic types
============

.. raw:: latex

    \footnotesize

.. include:: ../../atomic_t.txt
   :literal:

.. raw:: latex

    \normalsize


code:
.. SPDX-License-Identifier: GPL-2.0
   This is a simple wrapper to bring memory-barriers.txt into the RST world
   until such a time as that file can be converted directly.

============================
Linux kernel memory barriers
============================

.. raw:: latex

    \footnotesize

.. include:: ../../memory-barriers.txt
   :literal:

.. raw:: latex

    \normalsize


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

======
XArray
======

:Author: Matthew Wilcox

Overview
========

The XArray is an abstract data type which behaves like a very large array
of pointers.  It meets many of the same needs as a hash or a conventional
resizable array.  Unlike a hash, it allows you to sensibly go to the
next or previous entry in a cache-efficient manner.  In contrast to a
resizable array, there is no need to copy data or change MMU mappings in
order to grow the array.  It is more memory-efficient, parallelisable
and cache friendly than a doubly-linked list.  It takes advantage of
RCU to perform lookups without locking.

The XArray implementation is efficient when the indices used are densely
clustered; hashing the object and using the hash as the index will not
perform well.  The XArray is optimised for small indices, but still has
good performance with large indices.  If your index can be larger than
``ULONG_MAX`` then the XArray is not the data type for you.  The most
important user of the XArray is the page cache.

Normal pointers may be stored in the XArray directly.  They must be 4-byte
aligned, which is true for any pointer returned from kmalloc() and
alloc_page().  It isn't true for arbitrary user-space pointers,
nor for function pointers.  You can store pointers to statically allocated
objects, as long as those objects have an alignment of at least 4.

You can also store integers between 0 and ``LONG_MAX`` in the XArray.
You must first convert it into an entry using xa_mk_value().
When you retrieve an entry from the XArray, you can check whether it is
a value entry by calling xa_is_value(), and convert it back to
an integer by calling xa_to_value().

Some users want to tag the pointers they store in the XArray.  You can
call xa_tag_pointer() to create an entry with a tag, xa_untag_pointer()
to turn a tagged entry back into an untagged pointer and xa_pointer_tag()
to retrieve the tag of an entry.  Tagged pointers use the same bits that
are used to distinguish value entries from normal pointers, so you must
decide whether they want to store value entries or tagged pointers in
any particular XArray.

The XArray does not support storing IS_ERR() pointers as some
conflict with value entries or internal entries.

An unusual feature of the XArray is the ability to create entries which
occupy a range of indices.  Once stored to, looking up any index in
the range will return the same entry as looking up any other index in
the range.  Storing to any index will store to all of them.  Multi-index
entries can be explicitly split into smaller entries, or storing ``NULL``
into any entry will cause the XArray to forget about the range.

Normal API
==========

Start by initialising an XArray, either with DEFINE_XARRAY()
for statically allocated XArrays or xa_init() for dynamically
allocated ones.  A freshly-initialised XArray contains a ``NULL``
pointer at every index.

You can then set entries using xa_store() and get entries
using xa_load().  xa_store will overwrite any entry with the
new entry and return the previous entry stored at that index.  You can
use xa_erase() instead of calling xa_store() with a
``NULL`` entry.  There is no difference between an entry that has never
been stored to, one that has been erased and one that has most recently
had ``NULL`` stored to it.

You can conditionally replace an entry at an index by using
xa_cmpxchg().  Like cmpxchg(), it will only succeed if
the entry at that index has the 'old' value.  It also returns the entry
which was at that index; if it returns the same entry which was passed as
'old', then xa_cmpxchg() succeeded.

If you want to only store a new entry to an index if the current entry
at that index is ``NULL``, you can use xa_insert() which
returns ``-EBUSY`` if the entry is not empty.

You can copy entries out of the XArray into a plain array by calling
xa_extract().  Or you can iterate over the present entries in the XArray
by calling xa_for_each(), xa_for_each_start() or xa_for_each_range().
You may prefer to use xa_find() or xa_find_after() to move to the next
present entry in the XArray.

Calling xa_store_range() stores the same entry in a range
of indices.  If you do this, some of the other operations will behave
in a slightly odd way.  For example, marking the entry at one index
may result in the entry being marked at some, but not all of the other
indices.  Storing into one index may result in the entry retrieved by
some, but not all of the other indices changing.

Sometimes you need to ensure that a subsequent call to xa_store()
will not need to allocate memory.  The xa_reserve() function
will store a reserved entry at the indicated index.  Users of the
normal API will see this entry as containing ``NULL``.  If you do
not need to use the reserved entry, you can call xa_release()
to remove the unused entry.  If another user has stored to the entry
in the meantime, xa_release() will do nothing; if instead you
want the entry to become ``NULL``, you should use xa_erase().
Using xa_insert() on a reserved entry will fail.

If all entries in the array are ``NULL``, the xa_empty() function
will return ``true``.

Finally, you can remove all entries from an XArray by calling
xa_destroy().  If the XArray entries are pointers, you may wish
to free the entries first.  You can do this by iterating over all present
entries in the XArray using the xa_for_each() iterator.

Search Marks
------------

Each entry in the array has three bits associated with it called marks.
Each mark may be set or cleared independently of the others.  You can
iterate over marked entries by using the xa_for_each_marked() iterator.

You can enquire whether a mark is set on an entry by using
xa_get_mark().  If the entry is not ``NULL``, you can set a mark on it
by using xa_set_mark() and remove the mark from an entry by calling
xa_clear_mark().  You can ask whether any entry in the XArray has a
particular mark set by calling xa_marked().  Erasing an entry from the
XArray causes all marks associated with that entry to be cleared.

Setting or clearing a mark on any index of a multi-index entry will
affect all indices covered by that entry.  Querying the mark on any
index will return the same result.

There is no way to iterate over entries which are not marked; the data
structure does not allow this to be implemented efficiently.  There are
not currently iterators to search for logical combinations of bits (eg
iterate over all entries which have both ``XA_MARK_1`` and ``XA_MARK_2``
set, or iterate over all entries which have ``XA_MARK_0`` or ``XA_MARK_2``
set).  It would be possible to add these if a user arises.

Allocating XArrays
------------------

If you use DEFINE_XARRAY_ALLOC() to define the XArray, or
initialise it by passing ``XA_FLAGS_ALLOC`` to xa_init_flags(),
the XArray changes to track whether entries are in use or not.

You can call xa_alloc() to store the entry at an unused index
in the XArray.  If you need to modify the array from interrupt context,
you can use xa_alloc_bh() or xa_alloc_irq() to disable
interrupts while allocating the ID.

Using xa_store(), xa_cmpxchg() or xa_insert() will
also mark the entry as being allocated.  Unlike a normal XArray, storing
``NULL`` will mark the entry as being in use, like xa_reserve().
To free an entry, use xa_erase() (or xa_release() if
you only want to free the entry if it's ``NULL``).

By default, the lowest free entry is allocated starting from 0.  If you
want to allocate entries starting at 1, it is more efficient to use
DEFINE_XARRAY_ALLOC1() or ``XA_FLAGS_ALLOC1``.  If you want to
allocate IDs up to a maximum, then wrap back around to the lowest free
ID, you can use xa_alloc_cyclic().

You cannot use ``XA_MARK_0`` with an allocating XArray as this mark
is used to track whether an entry is free or not.  The other marks are
available for your use.

Memory allocation
-----------------

The xa_store(), xa_cmpxchg(), xa_alloc(),
xa_reserve() and xa_insert() functions take a gfp_t
parameter in case the XArray needs to allocate memory to store this entry.
If the entry is being deleted, no memory allocation needs to be performed,
and the GFP flags specified will be ignored.

It is possible for no memory to be allocatable, particularly if you pass
a restrictive set of GFP flags.  In that case, the functions return a
special value which can be turned into an errno using xa_err().
If you don't need to know exactly which error occurred, using
xa_is_err() is slightly more efficient.

Locking
-------

When using the Normal API, you do not have to worry about locking.
The XArray uses RCU and an internal spinlock to synchronise access:

No lock needed:
 * xa_empty()
 * xa_marked()

Takes RCU read lock:
 * xa_load()
 * xa_for_each()
 * xa_for_each_start()
 * xa_for_each_range()
 * xa_find()
 * xa_find_after()
 * xa_extract()
 * xa_get_mark()

Takes xa_lock internally:
 * xa_store()
 * xa_store_bh()
 * xa_store_irq()
 * xa_insert()
 * xa_insert_bh()
 * xa_insert_irq()
 * xa_erase()
 * xa_erase_bh()
 * xa_erase_irq()
 * xa_cmpxchg()
 * xa_cmpxchg_bh()
 * xa_cmpxchg_irq()
 * xa_store_range()
 * xa_alloc()
 * xa_alloc_bh()
 * xa_alloc_irq()
 * xa_reserve()
 * xa_reserve_bh()
 * xa_reserve_irq()
 * xa_destroy()
 * xa_set_mark()
 * xa_clear_mark()

Assumes xa_lock held on entry:
 * __xa_store()
 * __xa_insert()
 * __xa_erase()
 * __xa_cmpxchg()
 * __xa_alloc()
 * __xa_set_mark()
 * __xa_clear_mark()

If you want to take advantage of the lock to protect the data structures
that you are storing in the XArray, you can call xa_lock()
before calling xa_load(), then take a reference count on the
object you have found before calling xa_unlock().  This will
prevent stores from removing the object from the array between looking
up the object and incrementing the refcount.  You can also use RCU to
avoid dereferencing freed memory, but an explanation of that is beyond
the scope of this document.

The XArray does not disable interrupts or softirqs while modifying
the array.  It is safe to read the XArray from interrupt or softirq
context as the RCU lock provides enough protection.

If, for example, you want to store entries in the XArray in process
context and then erase them in softirq context, you can do that this way::

    void foo_init(struct foo *foo)
    {
        xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
    }

    int foo_store(struct foo *foo, unsigned long index, void *entry)
    {
        int err;

        xa_lock_bh(&foo->array);
        err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
        if (!err)
            foo->count++;
        xa_unlock_bh(&foo->array);
        return err;
    }

    /* foo_erase() is only called from softirq context */
    void foo_erase(struct foo *foo, unsigned long index)
    {
        xa_lock(&foo->array);
        __xa_erase(&foo->array, index);
        foo->count--;
        xa_unlock(&foo->array);
    }

If you are going to modify the XArray from interrupt or softirq context,
you need to initialise the array using xa_init_flags(), passing
``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``.

The above example also shows a common pattern of wanting to extend the
coverage of the xa_lock on the store side to protect some statistics
associated with the array.

Sharing the XArray with interrupt context is also possible, either
using xa_lock_irqsave() in both the interrupt handler and process
context, or xa_lock_irq() in process context and xa_lock()
in the interrupt handler.  Some of the more common patterns have helper
functions such as xa_store_bh(), xa_store_irq(),
xa_erase_bh(), xa_erase_irq(), xa_cmpxchg_bh()
and xa_cmpxchg_irq().

Sometimes you need to protect access to the XArray with a mutex because
that lock sits above another mutex in the locking hierarchy.  That does
not entitle you to use functions like __xa_erase() without taking
the xa_lock; the xa_lock is used for lockdep validation and will be used
for other purposes in the future.

The __xa_set_mark() and __xa_clear_mark() functions are also
available for situations where you look up an entry and want to atomically
set or clear a mark.  It may be more efficient to use the advanced API
in this case, as it will save you from walking the tree twice.

Advanced API
============

The advanced API offers more flexibility and better performance at the
cost of an interface which can be harder to use and has fewer safeguards.
No locking is done for you by the advanced API, and you are required
to use the xa_lock while modifying the array.  You can choose whether
to use the xa_lock or the RCU lock while doing read-only operations on
the array.  You can mix advanced and normal operations on the same array;
indeed the normal API is implemented in terms of the advanced API.  The
advanced API is only available to modules with a GPL-compatible license.

The advanced API is based around the xa_state.  This is an opaque data
structure which you declare on the stack using the XA_STATE() macro.
This macro initialises the xa_state ready to start walking around the
XArray.  It is used as a cursor to maintain the position in the XArray
and let you compose various operations together without having to restart
from the top every time.  The contents of the xa_state are protected by
the rcu_read_lock() or the xas_lock().  If you need to drop whichever of
those locks is protecting your state and tree, you must call xas_pause()
so that future calls do not rely on the parts of the state which were
left unprotected.

The xa_state is also used to store errors.  You can call
xas_error() to retrieve the error.  All operations check whether
the xa_state is in an error state before proceeding, so there's no need
for you to check for an error after each call; you can make multiple
calls in succession and only check at a convenient point.  The only
errors currently generated by the XArray code itself are ``ENOMEM`` and
``EINVAL``, but it supports arbitrary errors in case you want to call
xas_set_err() yourself.

If the xa_state is holding an ``ENOMEM`` error, calling xas_nomem()
will attempt to allocate more memory using the specified gfp flags and
cache it in the xa_state for the next attempt.  The idea is that you take
the xa_lock, attempt the operation and drop the lock.  The operation
attempts to allocate memory while holding the lock, but it is more
likely to fail.  Once you have dropped the lock, xas_nomem()
can try harder to allocate more memory.  It will return ``true`` if it
is worth retrying the operation (i.e. that there was a memory error *and*
more memory was allocated).  If it has previously allocated memory, and
that memory wasn't used, and there is no error (or some error that isn't
``ENOMEM``), then it will free the memory previously allocated.

Internal Entries
----------------

The XArray reserves some entries for its own purposes.  These are never
exposed through the normal API, but when using the advanced API, it's
possible to see them.  Usually the best way to handle them is to pass them
to xas_retry(), and retry the operation if it returns ``true``.

.. flat-table::
   :widths: 1 1 6

   * - Name
     - Test
     - Usage

   * - Node
     - xa_is_node()
     - An XArray node.  May be visible when using a multi-index xa_state.

   * - Sibling
     - xa_is_sibling()
     - A non-canonical entry for a multi-index entry.  The value indicates
       which slot in this node has the canonical entry.

   * - Retry
     - xa_is_retry()
     - This entry is currently being modified by a thread which has the
       xa_lock.  The node containing this entry may be freed at the end
       of this RCU period.  You should restart the lookup from the head
       of the array.

   * - Zero
     - xa_is_zero()
     - Zero entries appear as ``NULL`` through the Normal API, but occupy
       an entry in the XArray which can be used to reserve the index for
       future use.  This is used by allocating XArrays for allocated entries
       which are ``NULL``.

Other internal entries may be added in the future.  As far as possible, they
will be handled by xas_retry().

Additional functionality
------------------------

The xas_create_range() function allocates all the necessary memory
to store every entry in a range.  It will set ENOMEM in the xa_state if
it cannot allocate memory.

You can use xas_init_marks() to reset the marks on an entry
to their default state.  This is usually all marks clear, unless the
XArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set
and all other marks are clear.  Replacing one entry with another using
xas_store() will not reset the marks on that entry; if you want
the marks reset, you should do that explicitly.

The xas_load() will walk the xa_state as close to the entry
as it can.  If you know the xa_state has already been walked to the
entry and need to check that the entry hasn't changed, you can use
xas_reload() to save a function call.

If you need to move to a different index in the XArray, call
xas_set().  This resets the cursor to the top of the tree, which
will generally make the next operation walk the cursor to the desired
spot in the tree.  If you want to move to the next or previous index,
call xas_next() or xas_prev().  Setting the index does
not walk the cursor around the array so does not require a lock to be
held, while moving to the next or previous index does.

You can search for the next present entry using xas_find().  This
is the equivalent of both xa_find() and xa_find_after();
if the cursor has been walked to an entry, then it will find the next
entry after the one currently referenced.  If not, it will return the
entry at the index of the xa_state.  Using xas_next_entry() to
move to the next present entry instead of xas_find() will save
a function call in the majority of cases at the expense of emitting more
inline code.

The xas_find_marked() function is similar.  If the xa_state has
not been walked, it will return the entry at the index of the xa_state,
if it is marked.  Otherwise, it will return the first marked entry after
the entry referenced by the xa_state.  The xas_next_marked()
function is the equivalent of xas_next_entry().

When iterating over a range of the XArray using xas_for_each()
or xas_for_each_marked(), it may be necessary to temporarily stop
the iteration.  The xas_pause() function exists for this purpose.
After you have done the necessary work and wish to resume, the xa_state
is in an appropriate state to continue the iteration after the entry
you last processed.  If you have interrupts disabled while iterating,
then it is good manners to pause the iteration and reenable interrupts
every ``XA_CHECK_SCHED`` entries.

The xas_get_mark(), xas_set_mark() and xas_clear_mark() functions require
the xa_state cursor to have been moved to the appropriate location in the
XArray; they will do nothing if you have called xas_pause() or xas_set()
immediately before.

You can call xas_set_update() to have a callback function
called each time the XArray updates a node.  This is used by the page
cache workingset code to maintain its list of nodes which contain only
shadow entries.

Multi-Index Entries
-------------------

The XArray has the ability to tie multiple indices together so that
operations on one index affect all indices.  For example, storing into
any index will change the value of the entry retrieved from any index.
Setting or clearing a mark on any index will set or clear the mark
on every index that is tied together.  The current implementation
only allows tying ranges which are aligned powers of two together;
eg indices 64-127 may be tied together, but 2-6 may not be.  This may
save substantial quantities of memory; for example tying 512 entries
together will save over 4kB.

You can create a multi-index entry by using XA_STATE_ORDER()
or xas_set_order() followed by a call to xas_store().
Calling xas_load() with a multi-index xa_state will walk the
xa_state to the right location in the tree, but the return value is not
meaningful, potentially being an internal entry or ``NULL`` even when there
is an entry stored within the range.  Calling xas_find_conflict()
will return the first entry within the range or ``NULL`` if there are no
entries in the range.  The xas_for_each_conflict() iterator will
iterate over every entry which overlaps the specified range.

If xas_load() encounters a multi-index entry, the xa_index
in the xa_state will not be changed.  When iterating over an XArray
or calling xas_find(), if the initial index is in the middle
of a multi-index entry, it will not be altered.  Subsequent calls
or iterations will move the index to the first index in the range.
Each entry will only be returned once, no matter how many indices it
occupies.

Using xas_next() or xas_prev() with a multi-index xa_state is not
supported.  Using either of these functions on a multi-index entry will
reveal sibling entries; these should be skipped over by the caller.

Storing ``NULL`` into any index of a multi-index entry will set the
entry at every index to ``NULL`` and dissolve the tie.  A multi-index
entry can be split into entries occupying smaller ranges by calling
xas_split_alloc() without the xa_lock held, followed by taking the lock
and calling xas_split().

Functions and structures
========================

.. kernel-doc:: include/linux/xarray.h
.. kernel-doc:: lib/xarray.c


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

=============================================================
General description of the CPUFreq core and CPUFreq notifiers
=============================================================

Authors:
	- Dominik Brodowski  <linux@brodo.de>
	- David Kimdon <dwhedon@debian.org>
	- Rafael J. Wysocki <rafael.j.wysocki@intel.com>
	- Viresh Kumar <viresh.kumar@linaro.org>

.. Contents:

   1.  CPUFreq core and interfaces
   2.  CPUFreq notifiers
   3.  CPUFreq Table Generation with Operating Performance Point (OPP)

1. General Information
======================

The CPUFreq core code is located in drivers/cpufreq/cpufreq.c. This
cpufreq code offers a standardized interface for the CPUFreq
architecture drivers (those pieces of code that do actual
frequency transitions), as well as to "notifiers". These are device
drivers or other part of the kernel that need to be informed of
policy changes (ex. thermal modules like ACPI) or of all
frequency changes (ex. timing code) or even need to force certain
speed limits (like LCD drivers on ARM architecture). Additionally, the
kernel "constant" loops_per_jiffy is updated on frequency changes
here.

Reference counting of the cpufreq policies is done by cpufreq_cpu_get
and cpufreq_cpu_put, which make sure that the cpufreq driver is
correctly registered with the core, and will not be unloaded until
cpufreq_put_cpu is called. That also ensures that the respective cpufreq
policy doesn't get freed while being used.

2. CPUFreq notifiers
====================

CPUFreq notifiers conform to the standard kernel notifier interface.
See linux/include/linux/notifier.h for details on notifiers.

There are two different CPUFreq notifiers - policy notifiers and
transition notifiers.

2.1 CPUFreq policy notifiers
----------------------------

These are notified when a new policy is created or removed.

The phase is specified in the second argument to the notifier.  The phase is
CPUFREQ_CREATE_POLICY when the policy is first created and it is
CPUFREQ_REMOVE_POLICY when the policy is removed.

The third argument, a ``void *pointer``, points to a struct cpufreq_policy
consisting of several values, including min, max (the lower and upper
frequencies (in kHz) of the new policy).

2.2 CPUFreq transition notifiers
--------------------------------

These are notified twice for each online CPU in the policy, when the
CPUfreq driver switches the CPU core frequency and this change has no
any external implications.

The second argument specifies the phase - CPUFREQ_PRECHANGE or
CPUFREQ_POSTCHANGE.

The third argument is a struct cpufreq_freqs with the following
values:

======	======================================
policy	a pointer to the struct cpufreq_policy
old	old frequency
new	new frequency
flags	flags of the cpufreq driver
======	======================================

3. CPUFreq Table Generation with Operating Performance Point (OPP)
==================================================================
For details about OPP, see Documentation/power/opp.rst

dev_pm_opp_init_cpufreq_table -
	This function provides a ready to use conversion routine to translate
	the OPP layer's internal information about the available frequencies
	into a format readily providable to cpufreq.

	.. Warning::

	   Do not use this function in interrupt context.

	Example::

	 soc_pm_init()
	 {
		/* Do things */
		r = dev_pm_opp_init_cpufreq_table(dev, &freq_table);
		if (!r)
			policy->freq_table = freq_table;
		/* Do other things */
	 }

	.. note::

	   This function is available only if CONFIG_CPU_FREQ is enabled in
	   addition to CONFIG_PM_OPP.

dev_pm_opp_free_cpufreq_table
	Free up the table allocated by dev_pm_opp_init_cpufreq_table