code:
.. include:: <isonum.txt>

==========================
Linux generic IRQ handling
==========================

:Copyright: |copy| 2005-2010: Thomas Gleixner
:Copyright: |copy| 2005-2006:  Ingo Molnar

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

The generic interrupt handling layer is designed to provide a complete
abstraction of interrupt handling for device drivers. It is able to
handle all the different types of interrupt controller hardware. Device
drivers use generic API functions to request, enable, disable and free
interrupts. The drivers do not have to know anything about interrupt
hardware details, so they can be used on different platforms without
code changes.

This documentation is provided to developers who want to implement an
interrupt subsystem based for their architecture, with the help of the
generic IRQ handling layer.

Rationale
=========

The original implementation of interrupt handling in Linux uses the
__do_IRQ() super-handler, which is able to deal with every type of
interrupt logic.

Originally, Russell King identified different types of handlers to build
a quite universal set for the ARM interrupt handler implementation in
Linux 2.5/2.6. He distinguished between:

-  Level type

-  Edge type

-  Simple type

During the implementation we identified another type:

-  Fast EOI type

In the SMP world of the __do_IRQ() super-handler another type was
identified:

-  Per CPU type

This split implementation of high-level IRQ handlers allows us to
optimize the flow of the interrupt handling for each specific interrupt
type. This reduces complexity in that particular code path and allows
the optimized handling of a given type.

The original general IRQ implementation used hw_interrupt_type
structures and their ``->ack``, ``->end`` [etc.] callbacks to differentiate
the flow control in the super-handler. This leads to a mix of flow logic
and low-level hardware logic, and it also leads to unnecessary code
duplication: for example in i386, there is an ``ioapic_level_irq`` and an
``ioapic_edge_irq`` IRQ-type which share many of the low-level details but
have different flow handling.

A more natural abstraction is the clean separation of the 'irq flow' and
the 'chip details'.

Analysing a couple of architecture's IRQ subsystem implementations
reveals that most of them can use a generic set of 'irq flow' methods
and only need to add the chip-level specific code. The separation is
also valuable for (sub)architectures which need specific quirks in the
IRQ flow itself but not in the chip details - and thus provides a more
transparent IRQ subsystem design.

Each interrupt descriptor is assigned its own high-level flow handler,
which is normally one of the generic implementations. (This high-level
flow handler implementation also makes it simple to provide
demultiplexing handlers which can be found in embedded platforms on
various architectures.)

The separation makes the generic interrupt handling layer more flexible
and extensible. For example, an (sub)architecture can use a generic
IRQ-flow implementation for 'level type' interrupts and add a
(sub)architecture specific 'edge type' implementation.

To make the transition to the new model easier and prevent the breakage
of existing implementations, the __do_IRQ() super-handler is still
available. This leads to a kind of duality for the time being. Over time
the new model should be used in more and more architectures, as it
enables smaller and cleaner IRQ subsystems. It's deprecated for three
years now and about to be removed.

Known Bugs And Assumptions
==========================

None (knock on wood).

Abstraction layers
==================

There are three main levels of abstraction in the interrupt code:

1. High-level driver API

2. High-level IRQ flow handlers

3. Chip-level hardware encapsulation

Interrupt control flow
----------------------

Each interrupt is described by an interrupt descriptor structure
irq_desc. The interrupt is referenced by an 'unsigned int' numeric
value which selects the corresponding interrupt description structure in
the descriptor structures array. The descriptor structure contains
status information and pointers to the interrupt flow method and the
interrupt chip structure which are assigned to this interrupt.

Whenever an interrupt triggers, the low-level architecture code calls
into the generic interrupt code by calling desc->handle_irq(). This
high-level IRQ handling function only uses desc->irq_data.chip
primitives referenced by the assigned chip descriptor structure.

High-level Driver API
---------------------

The high-level Driver API consists of following functions:

-  request_irq()

-  request_threaded_irq()

-  free_irq()

-  disable_irq()

-  enable_irq()

-  disable_irq_nosync() (SMP only)

-  synchronize_irq() (SMP only)

-  irq_set_irq_type()

-  irq_set_irq_wake()

-  irq_set_handler_data()

-  irq_set_chip()

-  irq_set_chip_data()

See the autogenerated function documentation for details.

High-level IRQ flow handlers
----------------------------

The generic layer provides a set of pre-defined irq-flow methods:

-  handle_level_irq()

-  handle_edge_irq()

-  handle_fasteoi_irq()

-  handle_simple_irq()

-  handle_percpu_irq()

-  handle_edge_eoi_irq()

-  handle_bad_irq()

The interrupt flow handlers (either pre-defined or architecture
specific) are assigned to specific interrupts by the architecture either
during bootup or during device initialization.

Default flow implementations
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Helper functions
^^^^^^^^^^^^^^^^

The helper functions call the chip primitives and are used by the
default flow implementations. The following helper functions are
implemented (simplified excerpt)::

    default_enable(struct irq_data *data)
    {
        desc->irq_data.chip->irq_unmask(data);
    }

    default_disable(struct irq_data *data)
    {
        if (!delay_disable(data))
            desc->irq_data.chip->irq_mask(data);
    }

    default_ack(struct irq_data *data)
    {
        chip->irq_ack(data);
    }

    default_mask_ack(struct irq_data *data)
    {
        if (chip->irq_mask_ack) {
            chip->irq_mask_ack(data);
        } else {
            chip->irq_mask(data);
            chip->irq_ack(data);
        }
    }

    noop(struct irq_data *data))
    {
    }

Default flow handler implementations
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Default Level IRQ flow handler
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

handle_level_irq provides a generic implementation for level-triggered
interrupts.

The following control flow is implemented (simplified excerpt)::

    desc->irq_data.chip->irq_mask_ack();
    handle_irq_event(desc->action);
    desc->irq_data.chip->irq_unmask();

Default Fast EOI IRQ flow handler
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

handle_fasteoi_irq provides a generic implementation for interrupts,
which only need an EOI at the end of the handler.

The following control flow is implemented (simplified excerpt)::

    handle_irq_event(desc->action);
    desc->irq_data.chip->irq_eoi();

Default Edge IRQ flow handler
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

handle_edge_irq provides a generic implementation for edge-triggered
interrupts.

The following control flow is implemented (simplified excerpt)::

    if (desc->status & running) {
        desc->irq_data.chip->irq_mask_ack();
        desc->status |= pending | masked;
        return;
    }
    desc->irq_data.chip->irq_ack();
    desc->status |= running;
    do {
        if (desc->status & masked)
            desc->irq_data.chip->irq_unmask();
        desc->status &= ~pending;
        handle_irq_event(desc->action);
    } while (status & pending);
    desc->status &= ~running;

Default simple IRQ flow handler
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

handle_simple_irq provides a generic implementation for simple
interrupts.

.. note::

   The simple flow handler does not call any handler/chip primitives.

The following control flow is implemented (simplified excerpt)::

    handle_irq_event(desc->action);

Default per CPU flow handler
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

handle_percpu_irq provides a generic implementation for per CPU
interrupts.

Per CPU interrupts are only available on SMP and the handler provides a
simplified version without locking.

The following control flow is implemented (simplified excerpt)::

    if (desc->irq_data.chip->irq_ack)
        desc->irq_data.chip->irq_ack();
    handle_irq_event(desc->action);
    if (desc->irq_data.chip->irq_eoi)
        desc->irq_data.chip->irq_eoi();

EOI Edge IRQ flow handler
^^^^^^^^^^^^^^^^^^^^^^^^^

handle_edge_eoi_irq provides an abnomination of the edge handler
which is solely used to tame a badly wreckaged irq controller on
powerpc/cell.

Bad IRQ flow handler
^^^^^^^^^^^^^^^^^^^^

handle_bad_irq is used for spurious interrupts which have no real
handler assigned..

Quirks and optimizations
~~~~~~~~~~~~~~~~~~~~~~~~

The generic functions are intended for 'clean' architectures and chips,
which have no platform-specific IRQ handling quirks. If an architecture
needs to implement quirks on the 'flow' level then it can do so by
overriding the high-level irq-flow handler.

Delayed interrupt disable
~~~~~~~~~~~~~~~~~~~~~~~~~

This per interrupt selectable feature, which was introduced by Russell
King in the ARM interrupt implementation, does not mask an interrupt at
the hardware level when disable_irq() is called. The interrupt is kept
enabled and is masked in the flow handler when an interrupt event
happens. This prevents losing edge interrupts on hardware which does not
store an edge interrupt event while the interrupt is disabled at the
hardware level. When an interrupt arrives while the IRQ_DISABLED flag
is set, then the interrupt is masked at the hardware level and the
IRQ_PENDING bit is set. When the interrupt is re-enabled by
enable_irq() the pending bit is checked and if it is set, the interrupt
is resent either via hardware or by a software resend mechanism. (It's
necessary to enable CONFIG_HARDIRQS_SW_RESEND when you want to use
the delayed interrupt disable feature and your hardware is not capable
of retriggering an interrupt.) The delayed interrupt disable is not
configurable.

Chip-level hardware encapsulation
---------------------------------

The chip-level hardware descriptor structure :c:type:`irq_chip` contains all
the direct chip relevant functions, which can be utilized by the irq flow
implementations.

-  ``irq_ack``

-  ``irq_mask_ack`` - Optional, recommended for performance

-  ``irq_mask``

-  ``irq_unmask``

-  ``irq_eoi`` - Optional, required for EOI flow handlers

-  ``irq_retrigger`` - Optional

-  ``irq_set_type`` - Optional

-  ``irq_set_wake`` - Optional

These primitives are strictly intended to mean what they say: ack means
ACK, masking means masking of an IRQ line, etc. It is up to the flow
handler(s) to use these basic units of low-level functionality.

__do_IRQ entry point
====================

The original implementation __do_IRQ() was an alternative entry point
for all types of interrupts. It no longer exists.

This handler turned out to be not suitable for all interrupt hardware
and was therefore reimplemented with split functionality for
edge/level/simple/percpu interrupts. This is not only a functional
optimization. It also shortens code paths for interrupts.

Locking on SMP
==============

The locking of chip registers is up to the architecture that defines the
chip primitives. The per-irq structure is protected via desc->lock, by
the generic layer.

Generic interrupt chip
======================

To avoid copies of identical implementations of IRQ chips the core
provides a configurable generic interrupt chip implementation.
Developers should check carefully whether the generic chip fits their
needs before implementing the same functionality slightly differently
themselves.

.. kernel-doc:: kernel/irq/generic-chip.c
   :export:

Structures
==========

This chapter contains the autogenerated documentation of the structures
which are used in the generic IRQ layer.

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

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

Public Functions Provided
=========================

This chapter contains the autogenerated documentation of the kernel API
functions which are exported.

.. kernel-doc:: kernel/irq/manage.c

.. kernel-doc:: kernel/irq/chip.c
   :export:

Internal Functions Provided
===========================

This chapter contains the autogenerated documentation of the internal
functions.

.. kernel-doc:: kernel/irq/irqdesc.c

.. kernel-doc:: kernel/irq/handle.c

.. kernel-doc:: kernel/irq/chip.c
   :internal:

Credits
=======

The following people have contributed to this document:

1. Thomas Gleixner tglx@linutronix.de

2. Ingo Molnar mingo@elte.hu


code:
.. _gfp_mask_from_fs_io:

=================================
GFP masks used from FS/IO context
=================================

:Date: May, 2018
:Author: Michal Hocko <mhocko@kernel.org>

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

Code paths in the filesystem and IO stacks must be careful when
allocating memory to prevent recursion deadlocks caused by direct
memory reclaim calling back into the FS or IO paths and blocking on
already held resources (e.g. locks - most commonly those used for the
transaction context).

The traditional way to avoid this deadlock problem is to clear __GFP_FS
respectively __GFP_IO (note the latter implies clearing the first as well) in
the gfp mask when calling an allocator. GFP_NOFS respectively GFP_NOIO can be
used as shortcut. It turned out though that above approach has led to
abuses when the restricted gfp mask is used "just in case" without a
deeper consideration which leads to problems because an excessive use
of GFP_NOFS/GFP_NOIO can lead to memory over-reclaim or other memory
reclaim issues.

New API
========

Since 4.12 we do have a generic scope API for both NOFS and NOIO context
``memalloc_nofs_save``, ``memalloc_nofs_restore`` respectively ``memalloc_noio_save``,
``memalloc_noio_restore`` which allow to mark a scope to be a critical
section from a filesystem or I/O point of view. Any allocation from that
scope will inherently drop __GFP_FS respectively __GFP_IO from the given
mask so no memory allocation can recurse back in the FS/IO.

.. kernel-doc:: include/linux/sched/mm.h
   :functions: memalloc_nofs_save memalloc_nofs_restore
.. kernel-doc:: include/linux/sched/mm.h
   :functions: memalloc_noio_save memalloc_noio_restore

FS/IO code then simply calls the appropriate save function before
any critical section with respect to the reclaim is started - e.g.
lock shared with the reclaim context or when a transaction context
nesting would be possible via reclaim. The restore function should be
called when the critical section ends. All that ideally along with an
explanation what is the reclaim context for easier maintenance.

Please note that the proper pairing of save/restore functions
allows nesting so it is safe to call ``memalloc_noio_save`` or
``memalloc_noio_restore`` respectively from an existing NOIO or NOFS
scope.

What about __vmalloc(GFP_NOFS)
==============================

vmalloc doesn't support GFP_NOFS semantic because there are hardcoded
GFP_KERNEL allocations deep inside the allocator which are quite non-trivial
to fix up. That means that calling ``vmalloc`` with GFP_NOFS/GFP_NOIO is
almost always a bug. The good news is that the NOFS/NOIO semantic can be
achieved by the scope API.

In the ideal world, upper layers should already mark dangerous contexts
and so no special care is required and vmalloc should be called without
any problems. Sometimes if the context is not really clear or there are
layering violations then the recommended way around that is to wrap ``vmalloc``
by the scope API with a comment explaining the problem.

repo_name: angery/linux


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

=============
ID Allocation
=============

:Author: Matthew Wilcox

Overview
========

A common problem to solve is allocating identifiers (IDs); generally
small numbers which identify a thing.  Examples include file descriptors,
process IDs, packet identifiers in networking protocols, SCSI tags
and device instance numbers.  The IDR and the IDA provide a reasonable
solution to the problem to avoid everybody inventing their own.  The IDR
provides the ability to map an ID to a pointer, while the IDA provides
only ID allocation, and as a result is much more memory-efficient.

The IDR interface is deprecated; please use the :doc:`XArray <xarray>`
instead.

IDR usage
=========

Start by initialising an IDR, either with DEFINE_IDR()
for statically allocated IDRs or idr_init() for dynamically
allocated IDRs.

You can call idr_alloc() to allocate an unused ID.  Look up
the pointer you associated with the ID by calling idr_find()
and free the ID by calling idr_remove().

If you need to change the pointer associated with an ID, you can call
idr_replace().  One common reason to do this is to reserve an
ID by passing a ``NULL`` pointer to the allocation function; initialise the
object with the reserved ID and finally insert the initialised object
into the IDR.

Some users need to allocate IDs larger than ``INT_MAX``.  So far all of
these users have been content with a ``UINT_MAX`` limit, and they use
idr_alloc_u32().  If you need IDs that will not fit in a u32,
we will work with you to address your needs.

If you need to allocate IDs sequentially, you can use
idr_alloc_cyclic().  The IDR becomes less efficient when dealing
with larger IDs, so using this function comes at a slight cost.

To perform an action on all pointers used by the IDR, you can
either use the callback-based idr_for_each() or the
iterator-style idr_for_each_entry().  You may need to use
idr_for_each_entry_continue() to continue an iteration.  You can
also use idr_get_next() if the iterator doesn't fit your needs.

When you have finished using an IDR, you can call idr_destroy()
to release the memory used by the IDR.  This will not free the objects
pointed to from the IDR; if you want to do that, use one of the iterators
to do it.

You can use idr_is_empty() to find out whether there are any
IDs currently allocated.

If you need to take a lock while allocating a new ID from the IDR,
you may need to pass a restrictive set of GFP flags, which can lead
to the IDR being unable to allocate memory.  To work around this,
you can call idr_preload() before taking the lock, and then
idr_preload_end() after the allocation.

.. kernel-doc:: include/linux/idr.h
   :doc: idr sync

IDA usage
=========

.. kernel-doc:: lib/idr.c
   :doc: IDA description

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

.. kernel-doc:: include/linux/idr.h
   :functions:
.. kernel-doc:: lib/idr.c
   :functions:


code:
======================
Core API Documentation
======================

This is the beginning of a manual for core kernel APIs.  The conversion
(and writing!) of documents for this manual is much appreciated!

Core utilities
==============

This section has general and "core core" documentation.  The first is a
massive grab-bag of kerneldoc info left over from the docbook days; it
should really be broken up someday when somebody finds the energy to do
it.

.. toctree::
   :maxdepth: 1

   kernel-api
   workqueue
   watch_queue
   printk-basics
   printk-formats
   printk-index
   symbol-namespaces
   asm-annotations

Data structures and low-level utilities
=======================================

Library functionality that is used throughout the kernel.

.. toctree::
   :maxdepth: 1

   kobject
   kref
   assoc_array
   xarray
   maple_tree
   idr
   circular-buffers
   rbtree
   generic-radix-tree
   packing
   this_cpu_ops
   timekeeping
   errseq
   wrappers/atomic_t
   wrappers/atomic_bitops

Low level entry and exit
========================

.. toctree::
   :maxdepth: 1

   entry

Concurrency primitives
======================

How Linux keeps everything from happening at the same time.  See
Documentation/locking/index.rst for more related documentation.

.. toctree::
   :maxdepth: 1

   refcount-vs-atomic
   irq/index
   local_ops
   padata
   ../RCU/index
   wrappers/memory-barriers.rst

Low-level hardware management
=============================

Cache management, managing CPU hotplug, etc.

.. toctree::
   :maxdepth: 1

   cachetlb
   cpu_hotplug
   memory-hotplug
   genericirq
   protection-keys

Memory management
=================

How to allocate and use memory in the kernel.  Note that there is a lot
more memory-management documentation in Documentation/mm/index.rst.

.. toctree::
   :maxdepth: 1

   memory-allocation
   unaligned-memory-access
   dma-api
   dma-api-howto
   dma-attributes
   dma-isa-lpc
   mm-api
   genalloc
   pin_user_pages
   boot-time-mm
   gfp_mask-from-fs-io

Interfaces for kernel debugging
===============================

.. toctree::
   :maxdepth: 1

   debug-objects
   tracepoint
   debugging-via-ohci1394

Everything else
===============

Documents that don't fit elsewhere or which have yet to be categorized.

.. toctree::
   :maxdepth: 1

   librs

.. only:: subproject and html

   Indices
   =======

   * :ref:`genindex`


code:
===============
What is an IRQ?
===============

An IRQ is an interrupt request from a device.
Currently they can come in over a pin, or over a packet.
Several devices may be connected to the same pin thus
sharing an IRQ.

An IRQ number is a kernel identifier used to talk about a hardware
interrupt source.  Typically this is an index into the global irq_desc
array, but except for what linux/interrupt.h implements the details
are architecture specific.

An IRQ number is an enumeration of the possible interrupt sources on a
machine.  Typically what is enumerated is the number of input pins on
all of the interrupt controller in the system.  In the case of ISA
what is enumerated are the 16 input pins on the two i8259 interrupt
controllers.

Architectures can assign additional meaning to the IRQ numbers, and
are encouraged to in the case  where there is any manual configuration
of the hardware involved.  The ISA IRQs are a classic example of
assigning this kind of additional meaning.


code:
====
IRQs
====

.. toctree::
   :maxdepth: 1

   concepts
   irq-affinity
   irq-domain
   irqflags-tracing


code:
================
SMP IRQ affinity
================

ChangeLog:
	- Started by Ingo Molnar <mingo@redhat.com>
	- Update by Max Krasnyansky <maxk@qualcomm.com>

/proc/irq/IRQ#/smp_affinity and /proc/irq/IRQ#/smp_affinity_list specify
which target CPUs are permitted for a given IRQ source.  It's a bitmask
(smp_affinity) or cpu list (smp_affinity_list) of allowed CPUs.  It's not
allowed to turn off all CPUs, and if an IRQ controller does not support
IRQ affinity then the value will not change from the default of all cpus.

/proc/irq/default_smp_affinity specifies default affinity mask that applies
to all non-active IRQs. Once IRQ is allocated/activated its affinity bitmask
will be set to the default mask. It can then be changed as described above.
Default mask is 0xffffffff.

Here is an example of restricting IRQ44 (eth1) to CPU0-3 then restricting
it to CPU4-7 (this is an 8-CPU SMP box)::

	[root@moon 44]# cd /proc/irq/44
	[root@moon 44]# cat smp_affinity
	ffffffff

	[root@moon 44]# echo 0f > smp_affinity
	[root@moon 44]# cat smp_affinity
	0000000f
	[root@moon 44]# ping -f h
	PING hell (195.4.7.3): 56 data bytes
	...
	--- hell ping statistics ---
	6029 packets transmitted, 6027 packets received, 0% packet loss
	round-trip min/avg/max = 0.1/0.1/0.4 ms
	[root@moon 44]# cat /proc/interrupts | grep 'CPU\|44:'
		CPU0       CPU1       CPU2       CPU3      CPU4       CPU5        CPU6       CPU7
	44:       1068       1785       1785       1783         0          0           0         0    IO-APIC-level  eth1

As can be seen from the line above IRQ44 was delivered only to the first four
processors (0-3).
Now lets restrict that IRQ to CPU(4-7).

::

	[root@moon 44]# echo f0 > smp_affinity
	[root@moon 44]# cat smp_affinity
	000000f0
	[root@moon 44]# ping -f h
	PING hell (195.4.7.3): 56 data bytes
	..
	--- hell ping statistics ---
	2779 packets transmitted, 2777 packets received, 0% packet loss
	round-trip min/avg/max = 0.1/0.5/585.4 ms
	[root@moon 44]# cat /proc/interrupts |  'CPU\|44:'
		CPU0       CPU1       CPU2       CPU3      CPU4       CPU5        CPU6       CPU7
	44:       1068       1785       1785       1783      1784       1069        1070       1069   IO-APIC-level  eth1

This time around IRQ44 was delivered only to the last four processors.
i.e counters for the CPU0-3 did not change.

Here is an example of limiting that same irq (44) to cpus 1024 to 1031::

	[root@moon 44]# echo 1024-1031 > smp_affinity_list
	[root@moon 44]# cat smp_affinity_list
	1024-1031

Note that to do this with a bitmask would require 32 bitmasks of zero
to follow the pertinent one.


code:
===============================================
The irq_domain interrupt number mapping library
===============================================

The current design of the Linux kernel uses a single large number
space where each separate IRQ source is assigned a different number.
This is simple when there is only one interrupt controller, but in
systems with multiple interrupt controllers the kernel must ensure
that each one gets assigned non-overlapping allocations of Linux
IRQ numbers.

The number of interrupt controllers registered as unique irqchips
show a rising tendency: for example subdrivers of different kinds
such as GPIO controllers avoid reimplementing identical callback
mechanisms as the IRQ core system by modelling their interrupt
handlers as irqchips, i.e. in effect cascading interrupt controllers.

Here the interrupt number loose all kind of correspondence to
hardware interrupt numbers: whereas in the past, IRQ numbers could
be chosen so they matched the hardware IRQ line into the root
interrupt controller (i.e. the component actually fireing the
interrupt line to the CPU) nowadays this number is just a number.

For this reason we need a mechanism to separate controller-local
interrupt numbers, called hardware irq's, from Linux IRQ numbers.

The irq_alloc_desc*() and irq_free_desc*() APIs provide allocation of
irq numbers, but they don't provide any support for reverse mapping of
the controller-local IRQ (hwirq) number into the Linux IRQ number
space.

The irq_domain library adds mapping between hwirq and IRQ numbers on
top of the irq_alloc_desc*() API.  An irq_domain to manage mapping is
preferred over interrupt controller drivers open coding their own
reverse mapping scheme.

irq_domain also implements translation from an abstract irq_fwspec
structure to hwirq numbers (Device Tree and ACPI GSI so far), and can
be easily extended to support other IRQ topology data sources.

irq_domain usage
================

An interrupt controller driver creates and registers an irq_domain by
calling one of the irq_domain_add_*() or irq_domain_create_*() functions
(each mapping method has a different allocator function, more on that later).
The function will return a pointer to the irq_domain on success. The caller
must provide the allocator function with an irq_domain_ops structure.

In most cases, the irq_domain will begin empty without any mappings
between hwirq and IRQ numbers.  Mappings are added to the irq_domain
by calling irq_create_mapping() which accepts the irq_domain and a
hwirq number as arguments.  If a mapping for the hwirq doesn't already
exist then it will allocate a new Linux irq_desc, associate it with
the hwirq, and call the .map() callback so the driver can perform any
required hardware setup.

Once a mapping has been established, it can be retrieved or used via a
variety of methods:

- irq_resolve_mapping() returns a pointer to the irq_desc structure
  for a given domain and hwirq number, and NULL if there was no
  mapping.
- irq_find_mapping() returns a Linux IRQ number for a given domain and
  hwirq number, and 0 if there was no mapping
- irq_linear_revmap() is now identical to irq_find_mapping(), and is
  deprecated
- generic_handle_domain_irq() handles an interrupt described by a
  domain and a hwirq number

Note that irq domain lookups must happen in contexts that are
compatible with a RCU read-side critical section.

The irq_create_mapping() function must be called *at least once*
before any call to irq_find_mapping(), lest the descriptor will not
be allocated.

If the driver has the Linux IRQ number or the irq_data pointer, and
needs to know the associated hwirq number (such as in the irq_chip
callbacks) then it can be directly obtained from irq_data->hwirq.

Types of irq_domain mappings
============================

There are several mechanisms available for reverse mapping from hwirq
to Linux irq, and each mechanism uses a different allocation function.
Which reverse map type should be used depends on the use case.  Each
of the reverse map types are described below:

Linear
------

::

	irq_domain_add_linear()
	irq_domain_create_linear()

The linear reverse map maintains a fixed size table indexed by the
hwirq number.  When a hwirq is mapped, an irq_desc is allocated for
the hwirq, and the IRQ number is stored in the table.

The Linear map is a good choice when the maximum number of hwirqs is
fixed and a relatively small number (~ < 256).  The advantages of this
map are fixed time lookup for IRQ numbers, and irq_descs are only
allocated for in-use IRQs.  The disadvantage is that the table must be
as large as the largest possible hwirq number.

irq_domain_add_linear() and irq_domain_create_linear() are functionally
equivalent, except for the first argument is different - the former
accepts an Open Firmware specific 'struct device_node', while the latter
accepts a more general abstraction 'struct fwnode_handle'.

The majority of drivers should use the linear map.

Tree
----

::

	irq_domain_add_tree()
	irq_domain_create_tree()

The irq_domain maintains a radix tree map from hwirq numbers to Linux
IRQs.  When an hwirq is mapped, an irq_desc is allocated and the
hwirq is used as the lookup key for the radix tree.

The tree map is a good choice if the hwirq number can be very large
since it doesn't need to allocate a table as large as the largest
hwirq number.  The disadvantage is that hwirq to IRQ number lookup is
dependent on how many entries are in the table.

irq_domain_add_tree() and irq_domain_create_tree() are functionally
equivalent, except for the first argument is different - the former
accepts an Open Firmware specific 'struct device_node', while the latter
accepts a more general abstraction 'struct fwnode_handle'.

Very few drivers should need this mapping.

No Map
------

::

	irq_domain_add_nomap()

The No Map mapping is to be used when the hwirq number is
programmable in the hardware.  In this case it is best to program the
Linux IRQ number into the hardware itself so that no mapping is
required.  Calling irq_create_direct_mapping() will allocate a Linux
IRQ number and call the .map() callback so that driver can program the
Linux IRQ number into the hardware.

Most drivers cannot use this mapping, and it is now gated on the
CONFIG_IRQ_DOMAIN_NOMAP option. Please refrain from introducing new
users of this API.

Legacy
------

::

	irq_domain_add_simple()
	irq_domain_add_legacy()
	irq_domain_create_simple()
	irq_domain_create_legacy()

The Legacy mapping is a special case for drivers that already have a
range of irq_descs allocated for the hwirqs.  It is used when the
driver cannot be immediately converted to use the linear mapping.  For
example, many embedded system board support files use a set of #defines
for IRQ numbers that are passed to struct device registrations.  In that
case the Linux IRQ numbers cannot be dynamically assigned and the legacy
mapping should be used.

As the name implies, the \*_legacy() functions are deprecated and only
exist to ease the support of ancient platforms. No new users should be
added. Same goes for the \*_simple() functions when their use results
in the legacy behaviour.

The legacy map assumes a contiguous range of IRQ numbers has already
been allocated for the controller and that the IRQ number can be
calculated by adding a fixed offset to the hwirq number, and
visa-versa.  The disadvantage is that it requires the interrupt
controller to manage IRQ allocations and it requires an irq_desc to be
allocated for every hwirq, even if it is unused.

The legacy map should only be used if fixed IRQ mappings must be
supported.  For example, ISA controllers would use the legacy map for
mapping Linux IRQs 0-15 so that existing ISA drivers get the correct IRQ
numbers.

Most users of legacy mappings should use irq_domain_add_simple() or
irq_domain_create_simple() which will use a legacy domain only if an IRQ range
is supplied by the system and will otherwise use a linear domain mapping.
The semantics of this call are such that if an IRQ range is specified then
descriptors will be allocated on-the-fly for it, and if no range is
specified it will fall through to irq_domain_add_linear() or
irq_domain_create_linear() which means *no* irq descriptors will be allocated.

A typical use case for simple domains is where an irqchip provider
is supporting both dynamic and static IRQ assignments.

In order to avoid ending up in a situation where a linear domain is
used and no descriptor gets allocated it is very important to make sure
that the driver using the simple domain call irq_create_mapping()
before any irq_find_mapping() since the latter will actually work
for the static IRQ assignment case.

irq_domain_add_simple() and irq_domain_create_simple() as well as
irq_domain_add_legacy() and irq_domain_create_legacy() are functionally
equivalent, except for the first argument is different - the former
accepts an Open Firmware specific 'struct device_node', while the latter
accepts a more general abstraction 'struct fwnode_handle'.

Hierarchy IRQ domain
--------------------

On some architectures, there may be multiple interrupt controllers
involved in delivering an interrupt from the device to the target CPU.
Let's look at a typical interrupt delivering path on x86 platforms::

  Device --> IOAPIC -> Interrupt remapping Controller -> Local APIC -> CPU

There are three interrupt controllers involved:

1) IOAPIC controller
2) Interrupt remapping controller
3) Local APIC controller

To support such a hardware topology and make software architecture match
hardware architecture, an irq_domain data structure is built for each
interrupt controller and those irq_domains are organized into hierarchy.
When building irq_domain hierarchy, the irq_domain near to the device is
child and the irq_domain near to CPU is parent. So a hierarchy structure
as below will be built for the example above::

	CPU Vector irq_domain (root irq_domain to manage CPU vectors)
		^
		|
	Interrupt Remapping irq_domain (manage irq_remapping entries)
		^
		|
	IOAPIC irq_domain (manage IOAPIC delivery entries/pins)

There are four major interfaces to use hierarchy irq_domain:

1) irq_domain_alloc_irqs(): allocate IRQ descriptors and interrupt
   controller related resources to deliver these interrupts.
2) irq_domain_free_irqs(): free IRQ descriptors and interrupt controller
   related resources associated with these interrupts.
3) irq_domain_activate_irq(): activate interrupt controller hardware to
   deliver the interrupt.
4) irq_domain_deactivate_irq(): deactivate interrupt controller hardware
   to stop delivering the interrupt.

Following changes are needed to support hierarchy irq_domain:

1) a new field 'parent' is added to struct irq_domain; it's used to
   maintain irq_domain hierarchy information.
2) a new field 'parent_data' is added to struct irq_data; it's used to
   build hierarchy irq_data to match hierarchy irq_domains. The irq_data
   is used to store irq_domain pointer and hardware irq number.
3) new callbacks are added to struct irq_domain_ops to support hierarchy
   irq_domain operations.

With support of hierarchy irq_domain and hierarchy irq_data ready, an
irq_domain structure is built for each interrupt controller, and an
irq_data structure is allocated for each irq_domain associated with an
IRQ. Now we could go one step further to support stacked(hierarchy)
irq_chip. That is, an irq_chip is associated with each irq_data along
the hierarchy. A child irq_chip may implement a required action by
itself or by cooperating with its parent irq_chip.

With stacked irq_chip, interrupt controller driver only needs to deal
with the hardware managed by itself and may ask for services from its
parent irq_chip when needed. So we could achieve a much cleaner
software architecture.

For an interrupt controller driver to support hierarchy irq_domain, it
needs to:

1) Implement irq_domain_ops.alloc and irq_domain_ops.free
2) Optionally implement irq_domain_ops.activate and
   irq_domain_ops.deactivate.
3) Optionally implement an irq_chip to manage the interrupt controller
   hardware.
4) No need to implement irq_domain_ops.map and irq_domain_ops.unmap,
   they are unused with hierarchy irq_domain.

Hierarchy irq_domain is in no way x86 specific, and is heavily used to
support other architectures, such as ARM, ARM64 etc.

Debugging
=========

Most of the internals of the IRQ subsystem are exposed in debugfs by
turning CONFIG_GENERIC_IRQ_DEBUGFS on.


code:
=======================
IRQ-flags state tracing
=======================

:Author: started by Ingo Molnar <mingo@redhat.com>

The "irq-flags tracing" feature "traces" hardirq and softirq state, in
that it gives interested subsystems an opportunity to be notified of
every hardirqs-off/hardirqs-on, softirqs-off/softirqs-on event that
happens in the kernel.

CONFIG_TRACE_IRQFLAGS_SUPPORT is needed for CONFIG_PROVE_SPIN_LOCKING
and CONFIG_PROVE_RW_LOCKING to be offered by the generic lock debugging
code. Otherwise only CONFIG_PROVE_MUTEX_LOCKING and
CONFIG_PROVE_RWSEM_LOCKING will be offered on an architecture - these
are locking APIs that are not used in IRQ context. (the one exception
for rwsems is worked around)

Architecture support for this is certainly not in the "trivial"
category, because lots of lowlevel assembly code deal with irq-flags
state changes. But an architecture can be irq-flags-tracing enabled in a
rather straightforward and risk-free manner.

Architectures that want to support this need to do a couple of
code-organizational changes first:

- add and enable TRACE_IRQFLAGS_SUPPORT in their arch level Kconfig file

and then a couple of functional changes are needed as well to implement
irq-flags-tracing support:

- in lowlevel entry code add (build-conditional) calls to the
  trace_hardirqs_off()/trace_hardirqs_on() functions. The lock validator
  closely guards whether the 'real' irq-flags matches the 'virtual'
  irq-flags state, and complains loudly (and turns itself off) if the
  two do not match. Usually most of the time for arch support for
  irq-flags-tracing is spent in this state: look at the lockdep
  complaint, try to figure out the assembly code we did not cover yet,
  fix and repeat. Once the system has booted up and works without a
  lockdep complaint in the irq-flags-tracing functions arch support is
  complete.
- if the architecture has non-maskable interrupts then those need to be
  excluded from the irq-tracing [and lock validation] mechanism via
  lockdep_off()/lockdep_on().

In general there is no risk from having an incomplete irq-flags-tracing
implementation in an architecture: lockdep will detect that and will
turn itself off. I.e. the lock validator will still be reliable. There
should be no crashes due to irq-tracing bugs. (except if the assembly
changes break other code by modifying conditions or registers that
shouldn't be)


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

List Management Functions
=========================

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

Basic C Library Functions
=========================

When writing drivers, you cannot in general use routines which are from
the C Library. Some of the functions have been found generally useful
and they are listed below. The behaviour of these functions may vary
slightly from those defined by ANSI, and these deviations are noted in
the text.

String Conversions
------------------

.. kernel-doc:: lib/vsprintf.c
   :export:

.. kernel-doc:: include/linux/kstrtox.h
   :functions: kstrtol kstrtoul

.. kernel-doc:: lib/kstrtox.c
   :export:

.. kernel-doc:: lib/string_helpers.c
   :export:

String Manipulation
-------------------

.. kernel-doc:: include/linux/fortify-string.h
   :internal:

.. kernel-doc:: lib/string.c
   :export:

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

.. kernel-doc:: mm/util.c
   :functions: kstrdup kstrdup_const kstrndup kmemdup kmemdup_nul memdup_user
               vmemdup_user strndup_user memdup_user_nul

Basic Kernel Library Functions
==============================

The Linux kernel provides more basic utility functions.

Bit Operations
--------------

.. kernel-doc:: include/asm-generic/bitops/instrumented-atomic.h
   :internal:

.. kernel-doc:: include/asm-generic/bitops/instrumented-non-atomic.h
   :internal:

.. kernel-doc:: include/asm-generic/bitops/instrumented-lock.h
   :internal:

Bitmap Operations
-----------------

.. kernel-doc:: lib/bitmap.c
   :doc: bitmap introduction

.. kernel-doc:: include/linux/bitmap.h
   :doc: declare bitmap

.. kernel-doc:: include/linux/bitmap.h
   :doc: bitmap overview

.. kernel-doc:: include/linux/bitmap.h
   :doc: bitmap bitops

.. kernel-doc:: lib/bitmap.c
   :export:

.. kernel-doc:: lib/bitmap.c
   :internal:

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

Command-line Parsing
--------------------

.. kernel-doc:: lib/cmdline.c
   :export:

Sorting
-------

.. kernel-doc:: lib/sort.c
   :export:

.. kernel-doc:: lib/list_sort.c
   :export:

Text Searching
--------------

.. kernel-doc:: lib/textsearch.c
   :doc: ts_intro

.. kernel-doc:: lib/textsearch.c
   :export:

.. kernel-doc:: include/linux/textsearch.h
   :functions: textsearch_find textsearch_next \
               textsearch_get_pattern textsearch_get_pattern_len

CRC and Math Functions in Linux
===============================

Arithmetic Overflow Checking
----------------------------

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

CRC Functions
-------------

.. kernel-doc:: lib/crc4.c
   :export:

.. kernel-doc:: lib/crc7.c
   :export:

.. kernel-doc:: lib/crc8.c
   :export:

.. kernel-doc:: lib/crc16.c
   :export:

.. kernel-doc:: lib/crc32.c

.. kernel-doc:: lib/crc-ccitt.c
   :export:

.. kernel-doc:: lib/crc-itu-t.c
   :export:

Base 2 log and power Functions
------------------------------

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

Integer power Functions
-----------------------

.. kernel-doc:: lib/math/int_pow.c
   :export:

.. kernel-doc:: lib/math/int_sqrt.c
   :export:

Division Functions
------------------

.. kernel-doc:: include/asm-generic/div64.h
   :functions: do_div

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

.. kernel-doc:: lib/math/gcd.c
   :export:

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

.. kernel-doc:: lib/uuid.c
   :export:

Kernel IPC facilities
=====================

IPC utilities
-------------

.. kernel-doc:: ipc/util.c
   :internal:

FIFO Buffer
===========

kfifo interface
---------------

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

relay interface support
=======================

Relay interface support is designed to provide an efficient mechanism
for tools and facilities to relay large amounts of data from kernel
space to user space.

relay interface
---------------

.. kernel-doc:: kernel/relay.c
   :export:

.. kernel-doc:: kernel/relay.c
   :internal:

Module Support
==============

Module Loading
--------------

.. kernel-doc:: kernel/kmod.c
   :export:

Inter Module support
--------------------

Refer to the files in kernel/module/ for more information.

Hardware Interfaces
===================

DMA Channels
------------

.. kernel-doc:: kernel/dma.c
   :export:

Resources Management
--------------------

.. kernel-doc:: kernel/resource.c
   :internal:

.. kernel-doc:: kernel/resource.c
   :export:

MTRR Handling
-------------

.. kernel-doc:: arch/x86/kernel/cpu/mtrr/mtrr.c
   :export:

Security Framework
==================

.. kernel-doc:: security/security.c
   :internal:

.. kernel-doc:: security/inode.c
   :export:

Audit Interfaces
================

.. kernel-doc:: kernel/audit.c
   :export:

.. kernel-doc:: kernel/auditsc.c
   :internal:

.. kernel-doc:: kernel/auditfilter.c
   :internal:

Accounting Framework
====================

.. kernel-doc:: kernel/acct.c
   :internal:

Block Devices
=============

.. kernel-doc:: include/linux/bio.h
.. kernel-doc:: block/blk-core.c
   :export:

.. kernel-doc:: block/blk-core.c
   :internal:

.. kernel-doc:: block/blk-map.c
   :export:

.. kernel-doc:: block/blk-sysfs.c
   :internal:

.. kernel-doc:: block/blk-settings.c
   :export:

.. kernel-doc:: block/blk-flush.c
   :export:

.. kernel-doc:: block/blk-lib.c
   :export:

.. kernel-doc:: block/blk-integrity.c
   :export:

.. kernel-doc:: kernel/trace/blktrace.c
   :internal:

.. kernel-doc:: block/genhd.c
   :internal:

.. kernel-doc:: block/genhd.c
   :export:

.. kernel-doc:: block/bdev.c
   :export:

Char devices
============

.. kernel-doc:: fs/char_dev.c
   :export:

Clock Framework
===============

The clock framework defines programming interfaces to support software
management of the system clock tree. This framework is widely used with
System-On-Chip (SOC) platforms to support power management and various
devices which may need custom clock rates. Note that these "clocks"
don't relate to timekeeping or real time clocks (RTCs), each of which
have separate frameworks. These :c:type:`struct clk <clk>`
instances may be used to manage for example a 96 MHz signal that is used
to shift bits into and out of peripherals or busses, or otherwise
trigger synchronous state machine transitions in system hardware.

Power management is supported by explicit software clock gating: unused
clocks are disabled, so the system doesn't waste power changing the
state of transistors that aren't in active use. On some systems this may
be backed by hardware clock gating, where clocks are gated without being
disabled in software. Sections of chips that are powered but not clocked
may be able to retain their last state. This low power state is often
called a *retention mode*. This mode still incurs leakage currents,
especially with finer circuit geometries, but for CMOS circuits power is
mostly used by clocked state changes.

Power-aware drivers only enable their clocks when the device they manage
is in active use. Also, system sleep states often differ according to
which clock domains are active: while a "standby" state may allow wakeup
from several active domains, a "mem" (suspend-to-RAM) state may require
a more wholesale shutdown of clocks derived from higher speed PLLs and
oscillators, limiting the number of possible wakeup event sources. A
driver's suspend method may need to be aware of system-specific clock
constraints on the target sleep state.

Some platforms support programmable clock generators. These can be used
by external chips of various kinds, such as other CPUs, multimedia
codecs, and devices with strict requirements for interface clocking.

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

Synchronization Primitives
==========================

Read-Copy Update (RCU)
----------------------

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

.. kernel-doc:: kernel/rcu/tree.c

.. kernel-doc:: kernel/rcu/tree_exp.h

.. kernel-doc:: kernel/rcu/update.c

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

.. kernel-doc:: kernel/rcu/srcutree.c

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

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

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

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

.. kernel-doc:: kernel/rcu/sync.c


code:
=====================================================================
Everything you never wanted to know about kobjects, ksets, and ktypes
=====================================================================

:Author: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
:Last updated: December 19, 2007

Based on an original article by Jon Corbet for lwn.net written October 1,
2003 and located at https://lwn.net/Articles/51437/

Part of the difficulty in understanding the driver model - and the kobject
abstraction upon which it is built - is that there is no obvious starting
place. Dealing with kobjects requires understanding a few different types,
all of which make reference to each other. In an attempt to make things
easier, we'll take a multi-pass approach, starting with vague terms and
adding detail as we go. To that end, here are some quick definitions of
some terms we will be working with.

 - A kobject is an object of type struct kobject.  Kobjects have a name
   and a reference count.  A kobject also has a parent pointer (allowing
   objects to be arranged into hierarchies), a specific type, and,
   usually, a representation in the sysfs virtual filesystem.

   Kobjects are generally not interesting on their own; instead, they are
   usually embedded within some other structure which contains the stuff
   the code is really interested in.

   No structure should **EVER** have more than one kobject embedded within it.
   If it does, the reference counting for the object is sure to be messed
   up and incorrect, and your code will be buggy.  So do not do this.

 - A ktype is the type of object that embeds a kobject.  Every structure
   that embeds a kobject needs a corresponding ktype.  The ktype controls
   what happens to the kobject when it is created and destroyed.

 - A kset is a group of kobjects.  These kobjects can be of the same ktype
   or belong to different ktypes.  The kset is the basic container type for
   collections of kobjects. Ksets contain their own kobjects, but you can
   safely ignore that implementation detail as the kset core code handles
   this kobject automatically.

   When you see a sysfs directory full of other directories, generally each
   of those directories corresponds to a kobject in the same kset.

We'll look at how to create and manipulate all of these types. A bottom-up
approach will be taken, so we'll go back to kobjects.

Embedding kobjects
==================

It is rare for kernel code to create a standalone kobject, with one major
exception explained below.  Instead, kobjects are used to control access to
a larger, domain-specific object.  To this end, kobjects will be found
embedded in other structures.  If you are used to thinking of things in
object-oriented terms, kobjects can be seen as a top-level, abstract class
from which other classes are derived.  A kobject implements a set of
capabilities which are not particularly useful by themselves, but are
nice to have in other objects.  The C language does not allow for the
direct expression of inheritance, so other techniques - such as structure
embedding - must be used.

(As an aside, for those familiar with the kernel linked list implementation,
this is analogous as to how "list_head" structs are rarely useful on
their own, but are invariably found embedded in the larger objects of
interest.)

So, for example, the UIO code in ``drivers/uio/uio.c`` has a structure that
defines the memory region associated with a uio device::

    struct uio_map {
            struct kobject kobj;
            struct uio_mem *mem;
    };

If you have a struct uio_map structure, finding its embedded kobject is
just a matter of using the kobj member.  Code that works with kobjects will
often have the opposite problem, however: given a struct kobject pointer,
what is the pointer to the containing structure?  You must avoid tricks
(such as assuming that the kobject is at the beginning of the structure)
and, instead, use the container_of() macro, found in ``<linux/kernel.h>``::

    container_of(ptr, type, member)

where:

  * ``ptr`` is the pointer to the embedded kobject,
  * ``type`` is the type of the containing structure, and
  * ``member`` is the name of the structure field to which ``pointer`` points.

The return value from container_of() is a pointer to the corresponding
container type. So, for example, a pointer ``kp`` to a struct kobject
embedded **within** a struct uio_map could be converted to a pointer to the
**containing** uio_map structure with::

    struct uio_map *u_map = container_of(kp, struct uio_map, kobj);

For convenience, programmers often define a simple macro for **back-casting**
kobject pointers to the containing type.  Exactly this happens in the
earlier ``drivers/uio/uio.c``, as you can see here::

    struct uio_map {
            struct kobject kobj;
            struct uio_mem *mem;
    };

    #define to_map(map) container_of(map, struct uio_map, kobj)

where the macro argument "map" is a pointer to the struct kobject in
question.  That macro is subsequently invoked with::

    struct uio_map *map = to_map(kobj);

Initialization of kobjects
==========================

Code which creates a kobject must, of course, initialize that object. Some
of the internal fields are setup with a (mandatory) call to kobject_init()::

    void kobject_init(struct kobject *kobj, const struct kobj_type *ktype);

The ktype is required for a kobject to be created properly, as every kobject
must have an associated kobj_type.  After calling kobject_init(), to
register the kobject with sysfs, the function kobject_add() must be called::

    int kobject_add(struct kobject *kobj, struct kobject *parent,
                    const char *fmt, ...);

This sets up the parent of the kobject and the name for the kobject
properly.  If the kobject is to be associated with a specific kset,
kobj->kset must be assigned before calling kobject_add().  If a kset is
associated with a kobject, then the parent for the kobject can be set to
NULL in the call to kobject_add() and then the kobject's parent will be the
kset itself.

As the name of the kobject is set when it is added to the kernel, the name
of the kobject should never be manipulated directly.  If you must change
the name of the kobject, call kobject_rename()::

    int kobject_rename(struct kobject *kobj, const char *new_name);

kobject_rename() does not perform any locking or have a solid notion of
what names are valid so the caller must provide their own sanity checking
and serialization.

There is a function called kobject_set_name() but that is legacy cruft and
is being removed.  If your code needs to call this function, it is
incorrect and needs to be fixed.

To properly access the name of the kobject, use the function
kobject_name()::

    const char *kobject_name(const struct kobject * kobj);

There is a helper function to both initialize and add the kobject to the
kernel at the same time, called surprisingly enough kobject_init_and_add()::

    int kobject_init_and_add(struct kobject *kobj, const struct kobj_type *ktype,
                             struct kobject *parent, const char *fmt, ...);

The arguments are the same as the individual kobject_init() and
kobject_add() functions described above.

Uevents
=======

After a kobject has been registered with the kobject core, you need to
announce to the world that it has been created.  This can be done with a
call to kobject_uevent()::

    int kobject_uevent(struct kobject *kobj, enum kobject_action action);

Use the **KOBJ_ADD** action for when the kobject is first added to the kernel.
This should be done only after any attributes or children of the kobject
have been initialized properly, as userspace will instantly start to look
for them when this call happens.

When the kobject is removed from the kernel (details on how to do that are
below), the uevent for **KOBJ_REMOVE** will be automatically created by the
kobject core, so the caller does not have to worry about doing that by
hand.

Reference counts
================

One of the key functions of a kobject is to serve as a reference counter
for the object in which it is embedded. As long as references to the object
exist, the object (and the code which supports it) must continue to exist.
The low-level functions for manipulating a kobject's reference counts are::

    struct kobject *kobject_get(struct kobject *kobj);
    void kobject_put(struct kobject *kobj);

A successful call to kobject_get() will increment the kobject's reference
counter and return the pointer to the kobject.

When a reference is released, the call to kobject_put() will decrement the
reference count and, possibly, free the object. Note that kobject_init()
sets the reference count to one, so the code which sets up the kobject will
need to do a kobject_put() eventually to release that reference.

Because kobjects are dynamic, they must not be declared statically or on
the stack, but instead, always allocated dynamically.  Future versions of
the kernel will contain a run-time check for kobjects that are created
statically and will warn the developer of this improper usage.

If all that you want to use a kobject for is to provide a reference counter
for your structure, please use the struct kref instead; a kobject would be
overkill.  For more information on how to use struct kref, please see the
file Documentation/core-api/kref.rst in the Linux kernel source tree.

Creating "simple" kobjects
==========================

Sometimes all that a developer wants is a way to create a simple directory
in the sysfs hierarchy, and not have to mess with the whole complication of
ksets, show and store functions, and other details.  This is the one
exception where a single kobject should be created.  To create such an
entry, use the function::

    struct kobject *kobject_create_and_add(const char *name, struct kobject *parent);

This function will create a kobject and place it in sysfs in the location
underneath the specified parent kobject.  To create simple attributes
associated with this kobject, use::

    int sysfs_create_file(struct kobject *kobj, const struct attribute *attr);

or::

    int sysfs_create_group(struct kobject *kobj, const struct attribute_group *grp);

Both types of attributes used here, with a kobject that has been created
with the kobject_create_and_add(), can be of type kobj_attribute, so no
special custom attribute is needed to be created.

See the example module, ``samples/kobject/kobject-example.c`` for an
implementation of a simple kobject and attributes.

ktypes and release methods
==========================

One important thing still missing from the discussion is what happens to a
kobject when its reference count reaches zero. The code which created the
kobject generally does not know when that will happen; if it did, there
would be little point in using a kobject in the first place. Even
predictable object lifecycles become more complicated when sysfs is brought
in as other portions of the kernel can get a reference on any kobject that
is registered in the system.

The end result is that a structure protected by a kobject cannot be freed
before its reference count goes to zero. The reference count is not under
the direct control of the code which created the kobject. So that code must
be notified asynchronously whenever the last reference to one of its
kobjects goes away.

Once you registered your kobject via kobject_add(), you must never use
kfree() to free it directly. The only safe way is to use kobject_put(). It
is good practice to always use kobject_put() after kobject_init() to avoid
errors creeping in.

This notification is done through a kobject's release() method. Usually
such a method has a form like::

    void my_object_release(struct kobject *kobj)
    {
            struct my_object *mine = container_of(kobj, struct my_object, kobj);

            /* Perform any additional cleanup on this object, then... */
            kfree(mine);
    }

One important point cannot be overstated: every kobject must have a
release() method, and the kobject must persist (in a consistent state)
until that method is called. If these constraints are not met, the code is
flawed. Note that the kernel will warn you if you forget to provide a
release() method.  Do not try to get rid of this warning by providing an
"empty" release function.

If all your cleanup function needs to do is call kfree(), then you must
create a wrapper function which uses container_of() to upcast to the correct
type (as shown in the example above) and then calls kfree() on the overall
structure.

Note, the name of the kobject is available in the release function, but it
must NOT be changed within this callback.  Otherwise there will be a memory
leak in the kobject core, which makes people unhappy.

Interestingly, the release() method is not stored in the kobject itself;
instead, it is associated with the ktype. So let us introduce struct
kobj_type::

    struct kobj_type {
            void (*release)(struct kobject *kobj);
            const struct sysfs_ops *sysfs_ops;
            const struct attribute_group **default_groups;
            const struct kobj_ns_type_operations *(*child_ns_type)(struct kobject *kobj);
            const void *(*namespace)(struct kobject *kobj);
            void (*get_ownership)(struct kobject *kobj, kuid_t *uid, kgid_t *gid);
    };

This structure is used to describe a particular type of kobject (or, more
correctly, of containing object). Every kobject needs to have an associated
kobj_type structure; a pointer to that structure must be specified when you
call kobject_init() or kobject_init_and_add().

The release field in struct kobj_type is, of course, a pointer to the
release() method for this type of kobject. The other two fields (sysfs_ops
and default_groups) control how objects of this type are represented in
sysfs; they are beyond the scope of this document.

The default_groups pointer is a list of default attributes that will be
automatically created for any kobject that is registered with this ktype.

ksets
=====

A kset is merely a collection of kobjects that want to be associated with
each other.  There is no restriction that they be of the same ktype, but be
very careful if they are not.

A kset serves these functions:

 - It serves as a bag containing a group of objects. A kset can be used by
   the kernel to track "all block devices" or "all PCI device drivers."

 - A kset is also a subdirectory in sysfs, where the associated kobjects
   with the kset can show up.  Every kset contains a kobject which can be
   set up to be the parent of other kobjects; the top-level directories of
   the sysfs hierarchy are constructed in this way.

 - Ksets can support the "hotplugging" of kobjects and influence how
   uevent events are reported to user space.

In object-oriented terms, "kset" is the top-level container class; ksets
contain their own kobject, but that kobject is managed by the kset code and
should not be manipulated by any other user.

A kset keeps its children in a standard kernel linked list.  Kobjects point
back to their containing kset via their kset field. In almost all cases,
the kobjects belonging to a kset have that kset (or, strictly, its embedded
kobject) in their parent.

As a kset contains a kobject within it, it should always be dynamically
created and never declared statically or on the stack.  To create a new
kset use::

  struct kset *kset_create_and_add(const char *name,
                                   const struct kset_uevent_ops *uevent_ops,
                                   struct kobject *parent_kobj);

When you are finished with the kset, call::

  void kset_unregister(struct kset *k);

to destroy it.  This removes the kset from sysfs and decrements its reference
count.  When the reference count goes to zero, the kset will be released.
Because other references to the kset may still exist, the release may happen
after kset_unregister() returns.

An example of using a kset can be seen in the
``samples/kobject/kset-example.c`` file in the kernel tree.

If a kset wishes to control the uevent operations of the kobjects
associated with it, it can use the struct kset_uevent_ops to handle it::

  struct kset_uevent_ops {
          int (* const filter)(struct kobject *kobj);
          const char *(* const name)(struct kobject *kobj);
          int (* const uevent)(struct kobject *kobj, struct kobj_uevent_env *env);
  };

The filter function allows a kset to prevent a uevent from being emitted to
userspace for a specific kobject.  If the function returns 0, the uevent
will not be emitted.

The name function will be called to override the default name of the kset
that the uevent sends to userspace.  By default, the name will be the same
as the kset itself, but this function, if present, can override that name.

The uevent function will be called when the uevent is about to be sent to
userspace to allow more environment variables to be added to the uevent.

One might ask how, exactly, a kobject is added to a kset, given that no
functions which perform that function have been presented.  The answer is
that this task is handled by kobject_add().  When a kobject is passed to
kobject_add(), its kset member should point to the kset to which the
kobject will belong.  kobject_add() will handle the rest.

If the kobject belonging to a kset has no parent kobject set, it will be
added to the kset's directory.  Not all members of a kset do necessarily
live in the kset directory.  If an explicit parent kobject is assigned
before the kobject is added, the kobject is registered with the kset, but
added below the parent kobject.

Kobject removal
===============

After a kobject has been registered with the kobject core successfully, it
must be cleaned up when the code is finished with it.  To do that, call
kobject_put().  By doing this, the kobject core will automatically clean up
all of the memory allocated by this kobject.  If a ``KOBJ_ADD`` uevent has been
sent for the object, a corresponding ``KOBJ_REMOVE`` uevent will be sent, and
any other sysfs housekeeping will be handled for the caller properly.

If you need to do a two-stage delete of the kobject (say you are not
allowed to sleep when you need to destroy the object), then call
kobject_del() which will unregister the kobject from sysfs.  This makes the
kobject "invisible", but it is not cleaned up, and the reference count of
the object is still the same.  At a later time call kobject_put() to finish
the cleanup of the memory associated with the kobject.

kobject_del() can be used to drop the reference to the parent object, if
circular references are constructed.  It is valid in some cases, that a
parent objects references a child.  Circular references _must_ be broken
with an explicit call to kobject_del(), so that a release functions will be
called, and the objects in the former circle release each other.

Example code to copy from
=========================

For a more complete example of using ksets and kobjects properly, see the
example programs ``samples/kobject/{kobject-example.c,kset-example.c}``,
which will be built as loadable modules if you select ``CONFIG_SAMPLE_KOBJECT``.


code:
===================================================
Adding reference counters (krefs) to kernel objects
===================================================

:Author: Corey Minyard <minyard@acm.org>
:Author: Thomas Hellstrom <thellstrom@vmware.com>

A lot of this was lifted from Greg Kroah-Hartman's 2004 OLS paper and
presentation on krefs, which can be found at:

  - http://www.kroah.com/linux/talks/ols_2004_kref_paper/Reprint-Kroah-Hartman-OLS2004.pdf
  - http://www.kroah.com/linux/talks/ols_2004_kref_talk/

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

krefs allow you to add reference counters to your objects.  If you
have objects that are used in multiple places and passed around, and
you don't have refcounts, your code is almost certainly broken.  If
you want refcounts, krefs are the way to go.

To use a kref, add one to your data structures like::

    struct my_data
    {
	.
	.
	struct kref refcount;
	.
	.
    };

The kref can occur anywhere within the data structure.

Initialization
==============

You must initialize the kref after you allocate it.  To do this, call
kref_init as so::

     struct my_data *data;

     data = kmalloc(sizeof(*data), GFP_KERNEL);
     if (!data)
            return -ENOMEM;
     kref_init(&data->refcount);

This sets the refcount in the kref to 1.

Kref rules
==========

Once you have an initialized kref, you must follow the following
rules:

1) If you make a non-temporary copy of a pointer, especially if
   it can be passed to another thread of execution, you must
   increment the refcount with kref_get() before passing it off::

       kref_get(&data->refcount);

   If you already have a valid pointer to a kref-ed structure (the
   refcount cannot go to zero) you may do this without a lock.

2) When you are done with a pointer, you must call kref_put()::

       kref_put(&data->refcount, data_release);

   If this is the last reference to the pointer, the release
   routine will be called.  If the code never tries to get
   a valid pointer to a kref-ed structure without already
   holding a valid pointer, it is safe to do this without
   a lock.

3) If the code attempts to gain a reference to a kref-ed structure
   without already holding a valid pointer, it must serialize access
   where a kref_put() cannot occur during the kref_get(), and the
   structure must remain valid during the kref_get().

For example, if you allocate some data and then pass it to another
thread to process::

    void data_release(struct kref *ref)
    {
	struct my_data *data = container_of(ref, struct my_data, refcount);
	kfree(data);
    }

    void more_data_handling(void *cb_data)
    {
	struct my_data *data = cb_data;
	.
	. do stuff with data here
	.
	kref_put(&data->refcount, data_release);
    }

    int my_data_handler(void)
    {
	int rv = 0;
	struct my_data *data;
	struct task_struct *task;
	data = kmalloc(sizeof(*data), GFP_KERNEL);
	if (!data)
		return -ENOMEM;
	kref_init(&data->refcount);

	kref_get(&data->refcount);
	task = kthread_run(more_data_handling, data, "more_data_handling");
	if (task == ERR_PTR(-ENOMEM)) {
		rv = -ENOMEM;
	        kref_put(&data->refcount, data_release);
		goto out;
	}

	.
	. do stuff with data here
	.
    out:
	kref_put(&data->refcount, data_release);
	return rv;
    }

This way, it doesn't matter what order the two threads handle the
data, the kref_put() handles knowing when the data is not referenced
any more and releasing it.  The kref_get() does not require a lock,
since we already have a valid pointer that we own a refcount for.  The
put needs no lock because nothing tries to get the data without
already holding a pointer.

In the above example, kref_put() will be called 2 times in both success
and error paths. This is necessary because the reference count got
incremented 2 times by kref_init() and kref_get().

Note that the "before" in rule 1 is very important.  You should never
do something like::

	task = kthread_run(more_data_handling, data, "more_data_handling");
	if (task == ERR_PTR(-ENOMEM)) {
		rv = -ENOMEM;
		goto out;
	} else
		/* BAD BAD BAD - get is after the handoff */
		kref_get(&data->refcount);

Don't assume you know what you are doing and use the above construct.
First of all, you may not know what you are doing.  Second, you may
know what you are doing (there are some situations where locking is
involved where the above may be legal) but someone else who doesn't
know what they are doing may change the code or copy the code.  It's
bad style.  Don't do it.

There are some situations where you can optimize the gets and puts.
For instance, if you are done with an object and enqueuing it for
something else or passing it off to something else, there is no reason
to do a get then a put::

	/* Silly extra get and put */
	kref_get(&obj->ref);
	enqueue(obj);
	kref_put(&obj->ref, obj_cleanup);

Just do the enqueue.  A comment about this is always welcome::

	enqueue(obj);
	/* We are done with obj, so we pass our refcount off
	   to the queue.  DON'T TOUCH obj AFTER HERE! */

The last rule (rule 3) is the nastiest one to handle.  Say, for
instance, you have a list of items that are each kref-ed, and you wish
to get the first one.  You can't just pull the first item off the list
and kref_get() it.  That violates rule 3 because you are not already
holding a valid pointer.  You must add a mutex (or some other lock).
For instance::

	static DEFINE_MUTEX(mutex);
	static LIST_HEAD(q);
	struct my_data
	{
		struct kref      refcount;
		struct list_head link;
	};

	static struct my_data *get_entry()
	{
		struct my_data *entry = NULL;
		mutex_lock(&mutex);
		if (!list_empty(&q)) {
			entry = container_of(q.next, struct my_data, link);
			kref_get(&entry->refcount);
		}
		mutex_unlock(&mutex);
		return entry;
	}

	static void release_entry(struct kref *ref)
	{
		struct my_data *entry = container_of(ref, struct my_data, refcount);

		list_del(&entry->link);
		kfree(entry);
	}

	static void put_entry(struct my_data *entry)
	{
		mutex_lock(&mutex);
		kref_put(&entry->refcount, release_entry);
		mutex_unlock(&mutex);
	}

The kref_put() return value is useful if you do not want to hold the
lock during the whole release operation.  Say you didn't want to call
kfree() with the lock held in the example above (since it is kind of
pointless to do so).  You could use kref_put() as follows::

	static void release_entry(struct kref *ref)
	{
		/* All work is done after the return from kref_put(). */
	}

	static void put_entry(struct my_data *entry)
	{
		mutex_lock(&mutex);
		if (kref_put(&entry->refcount, release_entry)) {
			list_del(&entry->link);
			mutex_unlock(&mutex);
			kfree(entry);
		} else
			mutex_unlock(&mutex);
	}

This is really more useful if you have to call other routines as part
of the free operations that could take a long time or might claim the
same lock.  Note that doing everything in the release routine is still
preferred as it is a little neater.

The above example could also be optimized using kref_get_unless_zero() in
the following way::

	static struct my_data *get_entry()
	{
		struct my_data *entry = NULL;
		mutex_lock(&mutex);
		if (!list_empty(&q)) {
			entry = container_of(q.next, struct my_data, link);
			if (!kref_get_unless_zero(&entry->refcount))
				entry = NULL;
		}
		mutex_unlock(&mutex);
		return entry;
	}

	static void release_entry(struct kref *ref)
	{
		struct my_data *entry = container_of(ref, struct my_data, refcount);

		mutex_lock(&mutex);
		list_del(&entry->link);
		mutex_unlock(&mutex);
		kfree(entry);
	}

	static void put_entry(struct my_data *entry)
	{
		kref_put(&entry->refcount, release_entry);
	}

Which is useful to remove the mutex lock around kref_put() in put_entry(), but
it's important that kref_get_unless_zero is enclosed in the same critical
section that finds the entry in the lookup table,
otherwise kref_get_unless_zero may reference already freed memory.
Note that it is illegal to use kref_get_unless_zero without checking its
return value. If you are sure (by already having a valid pointer) that
kref_get_unless_zero() will return true, then use kref_get() instead.

Krefs and RCU
=============

The function kref_get_unless_zero also makes it possible to use rcu
locking for lookups in the above example::

	struct my_data
	{
		struct rcu_head rhead;
		.
		struct kref refcount;
		.
		.
	};

	static struct my_data *get_entry_rcu()
	{
		struct my_data *entry = NULL;
		rcu_read_lock();
		if (!list_empty(&q)) {
			entry = container_of(q.next, struct my_data, link);
			if (!kref_get_unless_zero(&entry->refcount))
				entry = NULL;
		}
		rcu_read_unlock();
		return entry;
	}

	static void release_entry_rcu(struct kref *ref)
	{
		struct my_data *entry = container_of(ref, struct my_data, refcount);

		mutex_lock(&mutex);
		list_del_rcu(&entry->link);
		mutex_unlock(&mutex);
		kfree_rcu(entry, rhead);
	}

	static void put_entry(struct my_data *entry)
	{
		kref_put(&entry->refcount, release_entry_rcu);
	}

But note that the struct kref member needs to remain in valid memory for a
rcu grace period after release_entry_rcu was called. That can be accomplished
by using kfree_rcu(entry, rhead) as done above, or by calling synchronize_rcu()
before using kfree, but note that synchronize_rcu() may sleep for a
substantial amount of time.


code:
==========================================
Reed-Solomon Library Programming Interface
==========================================

:Author: Thomas Gleixner

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

The generic Reed-Solomon Library provides encoding, decoding and error
correction functions.

Reed-Solomon codes are used in communication and storage applications to
ensure data integrity.

This documentation is provided for developers who want to utilize the
functions provided by the library.

Known Bugs And Assumptions
==========================

None.

Usage
=====

This chapter provides examples of how to use the library.

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

The init function init_rs returns a pointer to an rs decoder structure,
which holds the necessary information for encoding, decoding and error
correction with the given polynomial. It either uses an existing
matching decoder or creates a new one. On creation all the lookup tables
for fast en/decoding are created. The function may take a while, so make
sure not to call it in critical code paths.

::

    /* the Reed Solomon control structure */
    static struct rs_control *rs_decoder;

    /* Symbolsize is 10 (bits)
     * Primitive polynomial is x^10+x^3+1
     * first consecutive root is 0
     * primitive element to generate roots = 1
     * generator polynomial degree (number of roots) = 6
     */
    rs_decoder = init_rs (10, 0x409, 0, 1, 6);

Encoding
--------

The encoder calculates the Reed-Solomon code over the given data length
and stores the result in the parity buffer. Note that the parity buffer
must be initialized before calling the encoder.

The expanded data can be inverted on the fly by providing a non-zero
inversion mask. The expanded data is XOR'ed with the mask. This is used
e.g. for FLASH ECC, where the all 0xFF is inverted to an all 0x00. The
Reed-Solomon code for all 0x00 is all 0x00. The code is inverted before
storing to FLASH so it is 0xFF too. This prevents that reading from an
erased FLASH results in ECC errors.

The databytes are expanded to the given symbol size on the fly. There is
no support for encoding continuous bitstreams with a symbol size != 8 at
the moment. If it is necessary it should be not a big deal to implement
such functionality.

::

    /* Parity buffer. Size = number of roots */
    uint16_t par[6];
    /* Initialize the parity buffer */
    memset(par, 0, sizeof(par));
    /* Encode 512 byte in data8. Store parity in buffer par */
    encode_rs8 (rs_decoder, data8, 512, par, 0);

Decoding
--------

The decoder calculates the syndrome over the given data length and the
received parity symbols and corrects errors in the data.

If a syndrome is available from a hardware decoder then the syndrome
calculation is skipped.

The correction of the data buffer can be suppressed by providing a
correction pattern buffer and an error location buffer to the decoder.
The decoder stores the calculated error location and the correction
bitmask in the given buffers. This is useful for hardware decoders which
use a weird bit ordering scheme.

The databytes are expanded to the given symbol size on the fly. There is
no support for decoding continuous bitstreams with a symbolsize != 8 at
the moment. If it is necessary it should be not a big deal to implement
such functionality.

Decoding with syndrome calculation, direct data correction
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

    /* Parity buffer. Size = number of roots */
    uint16_t par[6];
    uint8_t  data[512];
    int numerr;
    /* Receive data */
    .....
    /* Receive parity */
    .....
    /* Decode 512 byte in data8.*/
    numerr = decode_rs8 (rs_decoder, data8, par, 512, NULL, 0, NULL, 0, NULL);

Decoding with syndrome given by hardware decoder, direct data correction
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

::

    /* Parity buffer. Size = number of roots */
    uint16_t par[6], syn[6];
    uint8_t  data[512];
    int numerr;
    /* Receive data */
    .....
    /* Receive parity */
    .....
    /* Get syndrome from hardware decoder */
    .....
    /* Decode 512 byte in data8.*/
    numerr = decode_rs8 (rs_decoder, data8, par, 512, syn, 0, NULL, 0, NULL);

Decoding with syndrome given by hardware decoder, no direct data correction.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Note: It's not necessary to give data and received parity to the
decoder.

::

    /* Parity buffer. Size = number of roots */
    uint16_t par[6], syn[6], corr[8];
    uint8_t  data[512];
    int numerr, errpos[8];
    /* Receive data */
    .....
    /* Receive parity */
    .....
    /* Get syndrome from hardware decoder */
    .....
    /* Decode 512 byte in data8.*/
    numerr = decode_rs8 (rs_decoder, NULL, NULL, 512, syn, 0, errpos, 0, corr);
    for (i = 0; i < numerr; i++) {
        do_error_correction_in_your_buffer(errpos[i], corr[i]);
    }

Cleanup
-------

The function free_rs frees the allocated resources, if the caller is
the last user of the decoder.

::

    /* Release resources */
    free_rs(rs_decoder);

Structures
==========

This chapter contains the autogenerated documentation of the structures
which are used in the Reed-Solomon Library and are relevant for a
developer.

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

Public Functions Provided
=========================

This chapter contains the autogenerated documentation of the
Reed-Solomon functions which are exported.

.. kernel-doc:: lib/reed_solomon/reed_solomon.c
   :export:

Credits
=======

The library code for encoding and decoding was written by Phil Karn.

::

            Copyright 2002, Phil Karn, KA9Q
            May be used under the terms of the GNU General Public License (GPL)

The wrapper functions and interfaces are written by Thomas Gleixner.

Many users have provided bugfixes, improvements and helping hands for
testing. Thanks a lot.

The following people have contributed to this document:

Thomas Gleixner\ tglx@linutronix.de


code:
.. _local_ops:

=================================================
Semantics and Behavior of Local Atomic Operations
=================================================

:Author: Mathieu Desnoyers

This document explains the purpose of the local atomic operations, how
to implement them for any given architecture and shows how they can be used
properly. It also stresses on the precautions that must be taken when reading
those local variables across CPUs when the order of memory writes matters.

.. note::

    Note that ``local_t`` based operations are not recommended for general
    kernel use. Please use the ``this_cpu`` operations instead unless there is
    really a special purpose. Most uses of ``local_t`` in the kernel have been
    replaced by ``this_cpu`` operations. ``this_cpu`` operations combine the
    relocation with the ``local_t`` like semantics in a single instruction and
    yield more compact and faster executing code.

Purpose of local atomic operations
==================================

Local atomic operations are meant to provide fast and highly reentrant per CPU
counters. They minimize the performance cost of standard atomic operations by
removing the LOCK prefix and memory barriers normally required to synchronize
across CPUs.

Having fast per CPU atomic counters is interesting in many cases: it does not
require disabling interrupts to protect from interrupt handlers and it permits
coherent counters in NMI handlers. It is especially useful for tracing purposes
and for various performance monitoring counters.

Local atomic operations only guarantee variable modification atomicity wrt the
CPU which owns the data. Therefore, care must taken to make sure that only one
CPU writes to the ``local_t`` data. This is done by using per cpu data and
making sure that we modify it from within a preemption safe context. It is
however permitted to read ``local_t`` data from any CPU: it will then appear to
be written out of order wrt other memory writes by the owner CPU.

Implementation for a given architecture
=======================================

It can be done by slightly modifying the standard atomic operations: only
their UP variant must be kept. It typically means removing LOCK prefix (on
i386 and x86_64) and any SMP synchronization barrier. If the architecture does
not have a different behavior between SMP and UP, including
``asm-generic/local.h`` in your architecture's ``local.h`` is sufficient.

The ``local_t`` type is defined as an opaque ``signed long`` by embedding an
``atomic_long_t`` inside a structure. This is made so a cast from this type to
a ``long`` fails. The definition looks like::

    typedef struct { atomic_long_t a; } local_t;

Rules to follow when using local atomic operations
==================================================

* Variables touched by local ops must be per cpu variables.
* *Only* the CPU owner of these variables must write to them.
* This CPU can use local ops from any context (process, irq, softirq, nmi, ...)
  to update its ``local_t`` variables.
* Preemption (or interrupts) must be disabled when using local ops in
  process context to make sure the process won't be migrated to a
  different CPU between getting the per-cpu variable and doing the
  actual local op.
* When using local ops in interrupt context, no special care must be
  taken on a mainline kernel, since they will run on the local CPU with
  preemption already disabled. I suggest, however, to explicitly
  disable preemption anyway to make sure it will still work correctly on
  -rt kernels.
* Reading the local cpu variable will provide the current copy of the
  variable.
* Reads of these variables can be done from any CPU, because updates to
  "``long``", aligned, variables are always atomic. Since no memory
  synchronization is done by the writer CPU, an outdated copy of the
  variable can be read when reading some *other* cpu's variables.

How to use local atomic operations
==================================

::

    #include <linux/percpu.h>
    #include <asm/local.h>

    static DEFINE_PER_CPU(local_t, counters) = LOCAL_INIT(0);

Counting
========

Counting is done on all the bits of a signed long.

In preemptible context, use ``get_cpu_var()`` and ``put_cpu_var()`` around
local atomic operations: it makes sure that preemption is disabled around write
access to the per cpu variable. For instance::

    local_inc(&get_cpu_var(counters));
    put_cpu_var(counters);

If you are already in a preemption-safe context, you can use
``this_cpu_ptr()`` instead::

    local_inc(this_cpu_ptr(&counters));

Reading the counters
====================

Those local counters can be read from foreign CPUs to sum the count. Note that
the data seen by local_read across CPUs must be considered to be out of order
relatively to other memory writes happening on the CPU that owns the data::

    long sum = 0;
    for_each_online_cpu(cpu)
            sum += local_read(&per_cpu(counters, cpu));

If you want to use a remote local_read to synchronize access to a resource
between CPUs, explicit ``smp_wmb()`` and ``smp_rmb()`` memory barriers must be used
respectively on the writer and the reader CPUs. It would be the case if you use
the ``local_t`` variable as a counter of bytes written in a buffer: there should
be a ``smp_wmb()`` between the buffer write and the counter increment and also a
``smp_rmb()`` between the counter read and the buffer read.

Here is a sample module which implements a basic per cpu counter using
``local.h``::

    /* test-local.c
     *
     * Sample module for local.h usage.
     */

    #include <asm/local.h>
    #include <linux/module.h>
    #include <linux/timer.h>

    static DEFINE_PER_CPU(local_t, counters) = LOCAL_INIT(0);

    static struct timer_list test_timer;

    /* IPI called on each CPU. */
    static void test_each(void *info)
    {
            /* Increment the counter from a non preemptible context */
            printk("Increment on cpu %d\n", smp_processor_id());
            local_inc(this_cpu_ptr(&counters));

            /* This is what incrementing the variable would look like within a
             * preemptible context (it disables preemption) :
             *
             * local_inc(&get_cpu_var(counters));
             * put_cpu_var(counters);
             */
    }

    static void do_test_timer(unsigned long data)
    {
            int cpu;

            /* Increment the counters */
            on_each_cpu(test_each, NULL, 1);
            /* Read all the counters */
            printk("Counters read from CPU %d\n", smp_processor_id());
            for_each_online_cpu(cpu) {
                    printk("Read : CPU %d, count %ld\n", cpu,
                            local_read(&per_cpu(counters, cpu)));
            }
            mod_timer(&test_timer, jiffies + 1000);
    }

    static int __init test_init(void)
    {
            /* initialize the timer that will increment the counter */
            timer_setup(&test_timer, do_test_timer, 0);
            mod_timer(&test_timer, jiffies + 1);

            return 0;
    }

    static void __exit test_exit(void)
    {
            timer_shutdown_sync(&test_timer);
    }

    module_init(test_init);
    module_exit(test_exit);

    MODULE_LICENSE("GPL");
    MODULE_AUTHOR("Mathieu Desnoyers");
    MODULE_DESCRIPTION("Local Atomic Ops");


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

==========
Maple Tree
==========

:Author: Liam R. Howlett

Overview
========

The Maple Tree is a B-Tree data type which is optimized for storing
non-overlapping ranges, including ranges of size 1.  The tree was designed to
be simple to use and does not require a user written search method.  It
supports iterating over a range of entries and going to the previous or next
entry in a cache-efficient manner.  The tree can also be put into an RCU-safe
mode of operation which allows reading and writing concurrently.  Writers must
synchronize on a lock, which can be the default spinlock, or the user can set
the lock to an external lock of a different type.

The Maple Tree maintains a small memory footprint and was designed to use
modern processor cache efficiently.  The majority of the users will be able to
use the normal API.  An :ref:`maple-tree-advanced-api` exists for more complex
scenarios.  The most important usage of the Maple Tree is the tracking of the
virtual memory areas.

The Maple Tree can store values between ``0`` and ``ULONG_MAX``.  The Maple
Tree reserves values with the bottom two bits set to '10' which are below 4096
(ie 2, 6, 10 .. 4094) for internal use.  If the entries may use reserved
entries then the users can convert the entries using xa_mk_value() and convert
them back by calling xa_to_value().  If the user needs to use a reserved
value, then the user can convert the value when using the
:ref:`maple-tree-advanced-api`, but are blocked by the normal API.

The Maple Tree can also be configured to support searching for a gap of a given
size (or larger).

Pre-allocating of nodes is also supported using the
:ref:`maple-tree-advanced-api`.  This is useful for users who must guarantee a
successful store operation within a given
code segment when allocating cannot be done.  Allocations of nodes are
relatively small at around 256 bytes.

.. _maple-tree-normal-api:

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

Start by initialising a maple tree, either with DEFINE_MTREE() for statically
allocated maple trees or mt_init() for dynamically allocated ones.  A
freshly-initialised maple tree contains a ``NULL`` pointer for the range ``0``
- ``ULONG_MAX``.  There are currently two types of maple trees supported: the
allocation tree and the regular tree.  The regular tree has a higher branching
factor for internal nodes.  The allocation tree has a lower branching factor
but allows the user to search for a gap of a given size or larger from either
``0`` upwards or ``ULONG_MAX`` down.  An allocation tree can be used by
passing in the ``MT_FLAGS_ALLOC_RANGE`` flag when initialising the tree.

You can then set entries using mtree_store() or mtree_store_range().
mtree_store() will overwrite any entry with the new entry and return 0 on
success or an error code otherwise.  mtree_store_range() works in the same way
but takes a range.  mtree_load() is used to retrieve the entry stored at a
given index.  You can use mtree_erase() to erase an entire range by only
knowing one value within that range, or mtree_store() call with an entry of
NULL may be used to partially erase a range or many ranges at once.

If you want to only store a new entry to a range (or index) if that range is
currently ``NULL``, you can use mtree_insert_range() or mtree_insert() which
return -EEXIST if the range is not empty.

You can search for an entry from an index upwards by using mt_find().

You can walk each entry within a range by calling mt_for_each().  You must
provide a temporary variable to store a cursor.  If you want to walk each
element of the tree then ``0`` and ``ULONG_MAX`` may be used as the range.  If
the caller is going to hold the lock for the duration of the walk then it is
worth looking at the mas_for_each() API in the :ref:`maple-tree-advanced-api`
section.

Sometimes it is necessary to ensure the next call to store to a maple tree does
not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.

Finally, you can remove all entries from a maple tree by calling
mtree_destroy().  If the maple tree entries are pointers, you may wish to free
the entries first.

Allocating Nodes
----------------

The allocations are handled by the internal tree code.  See
:ref:`maple-tree-advanced-alloc` for other options.

Locking
-------

You do not have to worry about locking.  See :ref:`maple-tree-advanced-locks`
for other options.

The Maple Tree uses RCU and an internal spinlock to synchronise access:

Takes RCU read lock:
 * mtree_load()
 * mt_find()
 * mt_for_each()
 * mt_next()
 * mt_prev()

Takes ma_lock internally:
 * mtree_store()
 * mtree_store_range()
 * mtree_insert()
 * mtree_insert_range()
 * mtree_erase()
 * mtree_destroy()
 * mt_set_in_rcu()
 * mt_clear_in_rcu()

If you want to take advantage of the internal lock to protect the data
structures that you are storing in the Maple Tree, you can call mtree_lock()
before calling mtree_load(), then take a reference count on the object you
have found before calling mtree_unlock().  This will prevent stores from
removing the object from the tree 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.

.. _maple-tree-advanced-api:

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.
You must take care of your own locking while using the advanced API.
You can use the ma_lock, RCU or an external lock for protection.
You can mix advanced and normal operations on the same array, as long
as the locking is compatible.  The :ref:`maple-tree-normal-api` is implemented
in terms of the advanced API.

The advanced API is based around the ma_state, this is where the 'mas'
prefix originates.  The ma_state struct keeps track of tree operations to make
life easier for both internal and external tree users.

Initialising the maple tree is the same as in the :ref:`maple-tree-normal-api`.
Please see above.

The maple state keeps track of the range start and end in mas->index and
mas->last, respectively.

mas_walk() will walk the tree to the location of mas->index and set the
mas->index and mas->last according to the range for the entry.

You can set entries using mas_store().  mas_store() will overwrite any entry
with the new entry and return the first existing entry that is overwritten.
The range is passed in as members of the maple state: index and last.

You can use mas_erase() to erase an entire range by setting index and
last of the maple state to the desired range to erase.  This will erase
the first range that is found in that range, set the maple state index
and last as the range that was erased and return the entry that existed
at that location.

You can walk each entry within a range by using mas_for_each().  If you want
to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as
the range.  If the lock needs to be periodically dropped, see the locking
section mas_pause().

Using a maple state allows mas_next() and mas_prev() to function as if the
tree was a linked list.  With such a high branching factor the amortized
performance penalty is outweighed by cache optimization.  mas_next() will
return the next entry which occurs after the entry at index.  mas_prev()
will return the previous entry which occurs before the entry at index.

mas_find() will find the first entry which exists at or above index on
the first call, and the next entry from every subsequent calls.

mas_find_rev() will find the fist entry which exists at or below the last on
the first call, and the previous entry from every subsequent calls.

If the user needs to yield the lock during an operation, then the maple state
must be paused using mas_pause().

There are a few extra interfaces provided when using an allocation tree.
If you wish to search for a gap within a range, then mas_empty_area()
or mas_empty_area_rev() can be used.  mas_empty_area() searches for a gap
starting at the lowest index given up to the maximum of the range.
mas_empty_area_rev() searches for a gap starting at the highest index given
and continues downward to the lower bound of the range.

.. _maple-tree-advanced-alloc:

Advanced Allocating Nodes
-------------------------

Allocations are usually handled internally to the tree, however if allocations
need to occur before a write occurs then calling mas_expected_entries() will
allocate the worst-case number of needed nodes to insert the provided number of
ranges.  This also causes the tree to enter mass insertion mode.  Once
insertions are complete calling mas_destroy() on the maple state will free the
unused allocations.

.. _maple-tree-advanced-locks:

Advanced Locking
----------------

The maple tree uses a spinlock by default, but external locks can be used for
tree updates as well.  To use an external lock, the tree must be initialized
with the ``MT_FLAGS_LOCK_EXTERN flag``, this is usually done with the
MTREE_INIT_EXT() #define, which takes an external lock as an argument.

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

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