code:
========================================
Generic Associative Array Implementation
========================================

Overview
========

This associative array implementation is an object container with the following
properties:

1. Objects are opaque pointers.  The implementation does not care where they
   point (if anywhere) or what they point to (if anything).

   .. note::

      Pointers to objects _must_ be zero in the least significant bit.

2. Objects do not need to contain linkage blocks for use by the array.  This
   permits an object to be located in multiple arrays simultaneously.
   Rather, the array is made up of metadata blocks that point to objects.

3. Objects require index keys to locate them within the array.

4. Index keys must be unique.  Inserting an object with the same key as one
   already in the array will replace the old object.

5. Index keys can be of any length and can be of different lengths.

6. Index keys should encode the length early on, before any variation due to
   length is seen.

7. Index keys can include a hash to scatter objects throughout the array.

8. The array can iterated over.  The objects will not necessarily come out in
   key order.

9. The array can be iterated over while it is being modified, provided the
   RCU readlock is being held by the iterator.  Note, however, under these
   circumstances, some objects may be seen more than once.  If this is a
   problem, the iterator should lock against modification.  Objects will not
   be missed, however, unless deleted.

10. Objects in the array can be looked up by means of their index key.

11. Objects can be looked up while the array is being modified, provided the
    RCU readlock is being held by the thread doing the look up.

The implementation uses a tree of 16-pointer nodes internally that are indexed
on each level by nibbles from the index key in the same manner as in a radix
tree.  To improve memory efficiency, shortcuts can be emplaced to skip over
what would otherwise be a series of single-occupancy nodes.  Further, nodes
pack leaf object pointers into spare space in the node rather than making an
extra branch until as such time an object needs to be added to a full node.

The Public API
==============

The public API can be found in ``<linux/assoc_array.h>``.  The associative
array is rooted on the following structure::

    struct assoc_array {
            ...
    };

The code is selected by enabling ``CONFIG_ASSOCIATIVE_ARRAY`` with::

    ./script/config -e ASSOCIATIVE_ARRAY

Edit Script
-----------

The insertion and deletion functions produce an 'edit script' that can later be
applied to effect the changes without risking ``ENOMEM``. This retains the
preallocated metadata blocks that will be installed in the internal tree and
keeps track of the metadata blocks that will be removed from the tree when the
script is applied.

This is also used to keep track of dead blocks and dead objects after the
script has been applied so that they can be freed later.  The freeing is done
after an RCU grace period has passed - thus allowing access functions to
proceed under the RCU read lock.

The script appears as outside of the API as a pointer of the type::

    struct assoc_array_edit;

There are two functions for dealing with the script:

1. Apply an edit script::

    void assoc_array_apply_edit(struct assoc_array_edit *edit);

This will perform the edit functions, interpolating various write barriers
to permit accesses under the RCU read lock to continue.  The edit script
will then be passed to ``call_rcu()`` to free it and any dead stuff it points
to.

2. Cancel an edit script::

    void assoc_array_cancel_edit(struct assoc_array_edit *edit);

This frees the edit script and all preallocated memory immediately. If
this was for insertion, the new object is _not_ released by this function,
but must rather be released by the caller.

These functions are guaranteed not to fail.

Operations Table
----------------

Various functions take a table of operations::

    struct assoc_array_ops {
            ...
    };

This points to a number of methods, all of which need to be provided:

1. Get a chunk of index key from caller data::

    unsigned long (*get_key_chunk)(const void *index_key, int level);

This should return a chunk of caller-supplied index key starting at the
*bit* position given by the level argument.  The level argument will be a
multiple of ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` and the function should return
``ASSOC_ARRAY_KEY_CHUNK_SIZE bits``.  No error is possible.

2. Get a chunk of an object's index key::

    unsigned long (*get_object_key_chunk)(const void *object, int level);

As the previous function, but gets its data from an object in the array
rather than from a caller-supplied index key.

3. See if this is the object we're looking for::

    bool (*compare_object)(const void *object, const void *index_key);

Compare the object against an index key and return ``true`` if it matches and
``false`` if it doesn't.

4. Diff the index keys of two objects::

    int (*diff_objects)(const void *object, const void *index_key);

Return the bit position at which the index key of the specified object
differs from the given index key or -1 if they are the same.

5. Free an object::

    void (*free_object)(void *object);

Free the specified object.  Note that this may be called an RCU grace period
after ``assoc_array_apply_edit()`` was called, so ``synchronize_rcu()`` may be
necessary on module unloading.

Manipulation Functions
----------------------

There are a number of functions for manipulating an associative array:

1. Initialise an associative array::

    void assoc_array_init(struct assoc_array *array);

This initialises the base structure for an associative array.  It can't fail.

2. Insert/replace an object in an associative array::

    struct assoc_array_edit *
    assoc_array_insert(struct assoc_array *array,
                       const struct assoc_array_ops *ops,
                       const void *index_key,
                       void *object);

This inserts the given object into the array.  Note that the least
significant bit of the pointer must be zero as it's used to type-mark
pointers internally.

If an object already exists for that key then it will be replaced with the
new object and the old one will be freed automatically.

The ``index_key`` argument should hold index key information and is
passed to the methods in the ops table when they are called.

This function makes no alteration to the array itself, but rather returns
an edit script that must be applied.  ``-ENOMEM`` is returned in the case of
an out-of-memory error.

The caller should lock exclusively against other modifiers of the array.

3. Delete an object from an associative array::

    struct assoc_array_edit *
    assoc_array_delete(struct assoc_array *array,
                       const struct assoc_array_ops *ops,
                       const void *index_key);

This deletes an object that matches the specified data from the array.

The ``index_key`` argument should hold index key information and is
passed to the methods in the ops table when they are called.

This function makes no alteration to the array itself, but rather returns
an edit script that must be applied.  ``-ENOMEM`` is returned in the case of
an out-of-memory error.  ``NULL`` will be returned if the specified object is
not found within the array.

The caller should lock exclusively against other modifiers of the array.

4. Delete all objects from an associative array::

    struct assoc_array_edit *
    assoc_array_clear(struct assoc_array *array,
                      const struct assoc_array_ops *ops);

This deletes all the objects from an associative array and leaves it
completely empty.

This function makes no alteration to the array itself, but rather returns
an edit script that must be applied.  ``-ENOMEM`` is returned in the case of
an out-of-memory error.

The caller should lock exclusively against other modifiers of the array.

5. Destroy an associative array, deleting all objects::

    void assoc_array_destroy(struct assoc_array *array,
                             const struct assoc_array_ops *ops);

This destroys the contents of the associative array and leaves it
completely empty.  It is not permitted for another thread to be traversing
the array under the RCU read lock at the same time as this function is
destroying it as no RCU deferral is performed on memory release -
something that would require memory to be allocated.

The caller should lock exclusively against other modifiers and accessors
of the array.

6. Garbage collect an associative array::

    int assoc_array_gc(struct assoc_array *array,
                       const struct assoc_array_ops *ops,
                       bool (*iterator)(void *object, void *iterator_data),
                       void *iterator_data);

This iterates over the objects in an associative array and passes each one to
``iterator()``.  If ``iterator()`` returns ``true``, the object is kept.  If it
returns ``false``, the object will be freed.  If the ``iterator()`` function
returns ``true``, it must perform any appropriate refcount incrementing on the
object before returning.

The internal tree will be packed down if possible as part of the iteration
to reduce the number of nodes in it.

The ``iterator_data`` is passed directly to ``iterator()`` and is otherwise
ignored by the function.

The function will return ``0`` if successful and ``-ENOMEM`` if there wasn't
enough memory.

It is possible for other threads to iterate over or search the array under
the RCU read lock while this function is in progress.  The caller should
lock exclusively against other modifiers of the array.

Access Functions
----------------

There are two functions for accessing an associative array:

1. Iterate over all the objects in an associative array::

    int assoc_array_iterate(const struct assoc_array *array,
                            int (*iterator)(const void *object,
                                            void *iterator_data),
                            void *iterator_data);

This passes each object in the array to the iterator callback function.
``iterator_data`` is private data for that function.

This may be used on an array at the same time as the array is being
modified, provided the RCU read lock is held.  Under such circumstances,
it is possible for the iteration function to see some objects twice.  If
this is a problem, then modification should be locked against.  The
iteration algorithm should not, however, miss any objects.

The function will return ``0`` if no objects were in the array or else it will
return the result of the last iterator function called.  Iteration stops
immediately if any call to the iteration function results in a non-zero
return.

2. Find an object in an associative array::

    void *assoc_array_find(const struct assoc_array *array,
                           const struct assoc_array_ops *ops,
                           const void *index_key);

This walks through the array's internal tree directly to the object
specified by the index key..

This may be used on an array at the same time as the array is being
modified, provided the RCU read lock is held.

The function will return the object if found (and set ``*_type`` to the object
type) or will return ``NULL`` if the object was not found.

Index Key Form
--------------

The index key can be of any form, but since the algorithms aren't told how long
the key is, it is strongly recommended that the index key includes its length
very early on before any variation due to the length would have an effect on
comparisons.

This will cause leaves with different length keys to scatter away from each
other - and those with the same length keys to cluster together.

It is also recommended that the index key begin with a hash of the rest of the
key to maximise scattering throughout keyspace.

The better the scattering, the wider and lower the internal tree will be.

Poor scattering isn't too much of a problem as there are shortcuts and nodes
can contain mixtures of leaves and metadata pointers.

The index key is read in chunks of machine word.  Each chunk is subdivided into
one nibble (4 bits) per level, so on a 32-bit CPU this is good for 8 levels and
on a 64-bit CPU, 16 levels.  Unless the scattering is really poor, it is
unlikely that more than one word of any particular index key will have to be
used.

Internal Workings
=================

The associative array data structure has an internal tree.  This tree is
constructed of two types of metadata blocks: nodes and shortcuts.

A node is an array of slots.  Each slot can contain one of four things:

* A NULL pointer, indicating that the slot is empty.
* A pointer to an object (a leaf).
* A pointer to a node at the next level.
* A pointer to a shortcut.

Basic Internal Tree Layout
--------------------------

Ignoring shortcuts for the moment, the nodes form a multilevel tree.  The index
key space is strictly subdivided by the nodes in the tree and nodes occur on
fixed levels.  For example::

 Level: 0               1               2               3
        =============== =============== =============== ===============
                                                        NODE D
                        NODE B          NODE C  +------>+---+
                +------>+---+   +------>+---+   |       | 0 |
        NODE A  |       | 0 |   |       | 0 |   |       +---+
        +---+   |       +---+   |       +---+   |       :   :
        | 0 |   |       :   :   |       :   :   |       +---+
        +---+   |       +---+   |       +---+   |       | f |
        | 1 |---+       | 3 |---+       | 7 |---+       +---+
        +---+           +---+           +---+
        :   :           :   :           | 8 |---+
        +---+           +---+           +---+   |       NODE E
        | e |---+       | f |           :   :   +------>+---+
        +---+   |       +---+           +---+           | 0 |
        | f |   |                       | f |           +---+
        +---+   |                       +---+           :   :
                |       NODE F                          +---+
                +------>+---+                           | f |
                        | 0 |           NODE G          +---+
                        +---+   +------>+---+
                        :   :   |       | 0 |
                        +---+   |       +---+
                        | 6 |---+       :   :
                        +---+           +---+
                        :   :           | f |
                        +---+           +---+
                        | f |
                        +---+

In the above example, there are 7 nodes (A-G), each with 16 slots (0-f).
Assuming no other meta data nodes in the tree, the key space is divided
thusly::

    KEY PREFIX      NODE
    ==========      ====
    137*            D
    138*            E
    13[0-69-f]*     C
    1[0-24-f]*      B
    e6*             G
    e[0-57-f]*      F
    [02-df]*        A

So, for instance, keys with the following example index keys will be found in
the appropriate nodes::

    INDEX KEY       PREFIX  NODE
    =============== ======= ====
    13694892892489  13      C
    13795289025897  137     D
    13889dde88793   138     E
    138bbb89003093  138     E
    1394879524789   12      C
    1458952489      1       B
    9431809de993ba  -       A
    b4542910809cd   -       A
    e5284310def98   e       F
    e68428974237    e6      G
    e7fffcbd443     e       F
    f3842239082     -       A

To save memory, if a node can hold all the leaves in its portion of keyspace,
then the node will have all those leaves in it and will not have any metadata
pointers - even if some of those leaves would like to be in the same slot.

A node can contain a heterogeneous mix of leaves and metadata pointers.
Metadata pointers must be in the slots that match their subdivisions of key
space.  The leaves can be in any slot not occupied by a metadata pointer.  It
is guaranteed that none of the leaves in a node will match a slot occupied by a
metadata pointer.  If the metadata pointer is there, any leaf whose key matches
the metadata key prefix must be in the subtree that the metadata pointer points
to.

In the above example list of index keys, node A will contain::

    SLOT    CONTENT         INDEX KEY (PREFIX)
    ====    =============== ==================
    1       PTR TO NODE B   1*
    any     LEAF            9431809de993ba
    any     LEAF            b4542910809cd
    e       PTR TO NODE F   e*
    any     LEAF            f3842239082

and node B::

    3	PTR TO NODE C	13*
    any	LEAF		1458952489

Shortcuts
---------

Shortcuts are metadata records that jump over a piece of keyspace.  A shortcut
is a replacement for a series of single-occupancy nodes ascending through the
levels.  Shortcuts exist to save memory and to speed up traversal.

It is possible for the root of the tree to be a shortcut - say, for example,
the tree contains at least 17 nodes all with key prefix ``1111``.  The
insertion algorithm will insert a shortcut to skip over the ``1111`` keyspace
in a single bound and get to the fourth level where these actually become
different.

Splitting And Collapsing Nodes
------------------------------

Each node has a maximum capacity of 16 leaves and metadata pointers.  If the
insertion algorithm finds that it is trying to insert a 17th object into a
node, that node will be split such that at least two leaves that have a common
key segment at that level end up in a separate node rooted on that slot for
that common key segment.

If the leaves in a full node and the leaf that is being inserted are
sufficiently similar, then a shortcut will be inserted into the tree.

When the number of objects in the subtree rooted at a node falls to 16 or
fewer, then the subtree will be collapsed down to a single node - and this will
ripple towards the root if possible.

Non-Recursive Iteration
-----------------------

Each node and shortcut contains a back pointer to its parent and the number of
slot in that parent that points to it.  None-recursive iteration uses these to
proceed rootwards through the tree, going to the parent node, slot N + 1 to
make sure progress is made without the need for a stack.

The backpointers, however, make simultaneous alteration and iteration tricky.

Simultaneous Alteration And Iteration
-------------------------------------

There are a number of cases to consider:

1. Simple insert/replace.  This involves simply replacing a NULL or old
   matching leaf pointer with the pointer to the new leaf after a barrier.
   The metadata blocks don't change otherwise.  An old leaf won't be freed
   until after the RCU grace period.

2. Simple delete.  This involves just clearing an old matching leaf.  The
   metadata blocks don't change otherwise.  The old leaf won't be freed until
   after the RCU grace period.

3. Insertion replacing part of a subtree that we haven't yet entered.  This
   may involve replacement of part of that subtree - but that won't affect
   the iteration as we won't have reached the pointer to it yet and the
   ancestry blocks are not replaced (the layout of those does not change).

4. Insertion replacing nodes that we're actively processing.  This isn't a
   problem as we've passed the anchoring pointer and won't switch onto the
   new layout until we follow the back pointers - at which point we've
   already examined the leaves in the replaced node (we iterate over all the
   leaves in a node before following any of its metadata pointers).

   We might, however, re-see some leaves that have been split out into a new
   branch that's in a slot further along than we were at.

5. Insertion replacing nodes that we're processing a dependent branch of.
   This won't affect us until we follow the back pointers.  Similar to (4).

6. Deletion collapsing a branch under us.  This doesn't affect us because the
   back pointers will get us back to the parent of the new node before we
   could see the new node.  The entire collapsed subtree is thrown away
   unchanged - and will still be rooted on the same slot, so we shouldn't
   process it a second time as we'll go back to slot + 1.

.. note::

   Under some circumstances, we need to simultaneously change the parent
   pointer and the parent slot pointer on a node (say, for example, we
   inserted another node before it and moved it up a level).  We cannot do
   this without locking against a read - so we have to replace that node too.

   However, when we're changing a shortcut into a node this isn't a problem
   as shortcuts only have one slot and so the parent slot number isn't used
   when traversing backwards over one.  This means that it's okay to change
   the slot number first - provided suitable barriers are used to make sure
   the parent slot number is read after the back pointer.

Obsolete blocks and leaves are freed up after an RCU grace period has passed,
so as long as anyone doing walking or iteration holds the RCU read lock, the
old superstructure should not go away on them.


code:
===========================
Boot time memory management
===========================

Early system initialization cannot use "normal" memory management
simply because it is not set up yet. But there is still need to
allocate memory for various data structures, for instance for the
physical page allocator.

A specialized allocator called ``memblock`` performs the
boot time memory management. The architecture specific initialization
must set it up in :c:func:`setup_arch` and tear it down in
:c:func:`mem_init` functions.

Once the early memory management is available it offers a variety of
functions and macros for memory allocations. The allocation request
may be directed to the first (and probably the only) node or to a
particular node in a NUMA system. There are API variants that panic
when an allocation fails and those that don't.

Memblock also offers a variety of APIs that control its own behaviour.

Memblock Overview
=================

.. kernel-doc:: mm/memblock.c
   :doc: memblock overview

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

Here is the description of memblock data structures, functions and
macros. Some of them are actually internal, but since they are
documented it would be silly to omit them. Besides, reading the
descriptions for the internal functions can help to understand what
really happens under the hood.

.. kernel-doc:: include/linux/memblock.h
.. kernel-doc:: mm/memblock.c
   :functions:

repo_name: angery/linux


code:
==================================
Cache and TLB Flushing Under Linux
==================================

:Author: David S. Miller <davem@redhat.com>

This document describes the cache/tlb flushing interfaces called
by the Linux VM subsystem.  It enumerates over each interface,
describes its intended purpose, and what side effect is expected
after the interface is invoked.

The side effects described below are stated for a uniprocessor
implementation, and what is to happen on that single processor.  The
SMP cases are a simple extension, in that you just extend the
definition such that the side effect for a particular interface occurs
on all processors in the system.  Don't let this scare you into
thinking SMP cache/tlb flushing must be so inefficient, this is in
fact an area where many optimizations are possible.  For example,
if it can be proven that a user address space has never executed
on a cpu (see mm_cpumask()), one need not perform a flush
for this address space on that cpu.

First, the TLB flushing interfaces, since they are the simplest.  The
"TLB" is abstracted under Linux as something the cpu uses to cache
virtual-->physical address translations obtained from the software
page tables.  Meaning that if the software page tables change, it is
possible for stale translations to exist in this "TLB" cache.
Therefore when software page table changes occur, the kernel will
invoke one of the following flush methods _after_ the page table
changes occur:

1) ``void flush_tlb_all(void)``

	The most severe flush of all.  After this interface runs,
	any previous page table modification whatsoever will be
	visible to the cpu.

	This is usually invoked when the kernel page tables are
	changed, since such translations are "global" in nature.

2) ``void flush_tlb_mm(struct mm_struct *mm)``

	This interface flushes an entire user address space from
	the TLB.  After running, this interface must make sure that
	any previous page table modifications for the address space
	'mm' will be visible to the cpu.  That is, after running,
	there will be no entries in the TLB for 'mm'.

	This interface is used to handle whole address space
	page table operations such as what happens during
	fork, and exec.

3) ``void flush_tlb_range(struct vm_area_struct *vma,
   unsigned long start, unsigned long end)``

	Here we are flushing a specific range of (user) virtual
	address translations from the TLB.  After running, this
	interface must make sure that any previous page table
	modifications for the address space 'vma->vm_mm' in the range
	'start' to 'end-1' will be visible to the cpu.  That is, after
	running, there will be no entries in the TLB for 'mm' for
	virtual addresses in the range 'start' to 'end-1'.

	The "vma" is the backing store being used for the region.
	Primarily, this is used for munmap() type operations.

	The interface is provided in hopes that the port can find
	a suitably efficient method for removing multiple page
	sized translations from the TLB, instead of having the kernel
	call flush_tlb_page (see below) for each entry which may be
	modified.

4) ``void flush_tlb_page(struct vm_area_struct *vma, unsigned long addr)``

	This time we need to remove the PAGE_SIZE sized translation
	from the TLB.  The 'vma' is the backing structure used by
	Linux to keep track of mmap'd regions for a process, the
	address space is available via vma->vm_mm.  Also, one may
	test (vma->vm_flags & VM_EXEC) to see if this region is
	executable (and thus could be in the 'instruction TLB' in
	split-tlb type setups).

	After running, this interface must make sure that any previous
	page table modification for address space 'vma->vm_mm' for
	user virtual address 'addr' will be visible to the cpu.  That
	is, after running, there will be no entries in the TLB for
	'vma->vm_mm' for virtual address 'addr'.

	This is used primarily during fault processing.

5) ``void update_mmu_cache(struct vm_area_struct *vma,
   unsigned long address, pte_t *ptep)``

	At the end of every page fault, this routine is invoked to
	tell the architecture specific code that a translation
	now exists at virtual address "address" for address space
	"vma->vm_mm", in the software page tables.

	A port may use this information in any way it so chooses.
	For example, it could use this event to pre-load TLB
	translations for software managed TLB configurations.
	The sparc64 port currently does this.

Next, we have the cache flushing interfaces.  In general, when Linux
is changing an existing virtual-->physical mapping to a new value,
the sequence will be in one of the following forms::

	1) flush_cache_mm(mm);
	   change_all_page_tables_of(mm);
	   flush_tlb_mm(mm);

	2) flush_cache_range(vma, start, end);
	   change_range_of_page_tables(mm, start, end);
	   flush_tlb_range(vma, start, end);

	3) flush_cache_page(vma, addr, pfn);
	   set_pte(pte_pointer, new_pte_val);
	   flush_tlb_page(vma, addr);

The cache level flush will always be first, because this allows
us to properly handle systems whose caches are strict and require
a virtual-->physical translation to exist for a virtual address
when that virtual address is flushed from the cache.  The HyperSparc
cpu is one such cpu with this attribute.

The cache flushing routines below need only deal with cache flushing
to the extent that it is necessary for a particular cpu.  Mostly,
these routines must be implemented for cpus which have virtually
indexed caches which must be flushed when virtual-->physical
translations are changed or removed.  So, for example, the physically
indexed physically tagged caches of IA32 processors have no need to
implement these interfaces since the caches are fully synchronized
and have no dependency on translation information.

Here are the routines, one by one:

1) ``void flush_cache_mm(struct mm_struct *mm)``

	This interface flushes an entire user address space from
	the caches.  That is, after running, there will be no cache
	lines associated with 'mm'.

	This interface is used to handle whole address space
	page table operations such as what happens during exit and exec.

2) ``void flush_cache_dup_mm(struct mm_struct *mm)``

	This interface flushes an entire user address space from
	the caches.  That is, after running, there will be no cache
	lines associated with 'mm'.

	This interface is used to handle whole address space
	page table operations such as what happens during fork.

	This option is separate from flush_cache_mm to allow some
	optimizations for VIPT caches.

3) ``void flush_cache_range(struct vm_area_struct *vma,
   unsigned long start, unsigned long end)``

	Here we are flushing a specific range of (user) virtual
	addresses from the cache.  After running, there will be no
	entries in the cache for 'vma->vm_mm' for virtual addresses in
	the range 'start' to 'end-1'.

	The "vma" is the backing store being used for the region.
	Primarily, this is used for munmap() type operations.

	The interface is provided in hopes that the port can find
	a suitably efficient method for removing multiple page
	sized regions from the cache, instead of having the kernel
	call flush_cache_page (see below) for each entry which may be
	modified.

4) ``void flush_cache_page(struct vm_area_struct *vma, unsigned long addr, unsigned long pfn)``

	This time we need to remove a PAGE_SIZE sized range
	from the cache.  The 'vma' is the backing structure used by
	Linux to keep track of mmap'd regions for a process, the
	address space is available via vma->vm_mm.  Also, one may
	test (vma->vm_flags & VM_EXEC) to see if this region is
	executable (and thus could be in the 'instruction cache' in
	"Harvard" type cache layouts).

	The 'pfn' indicates the physical page frame (shift this value
	left by PAGE_SHIFT to get the physical address) that 'addr'
	translates to.  It is this mapping which should be removed from
	the cache.

	After running, there will be no entries in the cache for
	'vma->vm_mm' for virtual address 'addr' which translates
	to 'pfn'.

	This is used primarily during fault processing.

5) ``void flush_cache_kmaps(void)``

	This routine need only be implemented if the platform utilizes
	highmem.  It will be called right before all of the kmaps
	are invalidated.

	After running, there will be no entries in the cache for
	the kernel virtual address range PKMAP_ADDR(0) to
	PKMAP_ADDR(LAST_PKMAP).

	This routing should be implemented in asm/highmem.h

6) ``void flush_cache_vmap(unsigned long start, unsigned long end)``
   ``void flush_cache_vunmap(unsigned long start, unsigned long end)``

	Here in these two interfaces we are flushing a specific range
	of (kernel) virtual addresses from the cache.  After running,
	there will be no entries in the cache for the kernel address
	space for virtual addresses in the range 'start' to 'end-1'.

	The first of these two routines is invoked after vmap_range()
	has installed the page table entries.  The second is invoked
	before vunmap_range() deletes the page table entries.

There exists another whole class of cpu cache issues which currently
require a whole different set of interfaces to handle properly.
The biggest problem is that of virtual aliasing in the data cache
of a processor.

Is your port susceptible to virtual aliasing in its D-cache?
Well, if your D-cache is virtually indexed, is larger in size than
PAGE_SIZE, and does not prevent multiple cache lines for the same
physical address from existing at once, you have this problem.

If your D-cache has this problem, first define asm/shmparam.h SHMLBA
properly, it should essentially be the size of your virtually
addressed D-cache (or if the size is variable, the largest possible
size).  This setting will force the SYSv IPC layer to only allow user
processes to mmap shared memory at address which are a multiple of
this value.

.. note::

  This does not fix shared mmaps, check out the sparc64 port for
  one way to solve this (in particular SPARC_FLAG_MMAPSHARED).

Next, you have to solve the D-cache aliasing issue for all
other cases.  Please keep in mind that fact that, for a given page
mapped into some user address space, there is always at least one more
mapping, that of the kernel in its linear mapping starting at
PAGE_OFFSET.  So immediately, once the first user maps a given
physical page into its address space, by implication the D-cache
aliasing problem has the potential to exist since the kernel already
maps this page at its virtual address.

  ``void copy_user_page(void *to, void *from, unsigned long addr, struct page *page)``
  ``void clear_user_page(void *to, unsigned long addr, struct page *page)``

	These two routines store data in user anonymous or COW
	pages.  It allows a port to efficiently avoid D-cache alias
	issues between userspace and the kernel.

	For example, a port may temporarily map 'from' and 'to' to
	kernel virtual addresses during the copy.  The virtual address
	for these two pages is chosen in such a way that the kernel
	load/store instructions happen to virtual addresses which are
	of the same "color" as the user mapping of the page.  Sparc64
	for example, uses this technique.

	The 'addr' parameter tells the virtual address where the
	user will ultimately have this page mapped, and the 'page'
	parameter gives a pointer to the struct page of the target.

	If D-cache aliasing is not an issue, these two routines may
	simply call memcpy/memset directly and do nothing more.

  ``void flush_dcache_page(struct page *page)``

        This routines must be called when:

	  a) the kernel did write to a page that is in the page cache page
	     and / or in high memory
	  b) the kernel is about to read from a page cache page and user space
	     shared/writable mappings of this page potentially exist.  Note
	     that {get,pin}_user_pages{_fast} already call flush_dcache_page
	     on any page found in the user address space and thus driver
	     code rarely needs to take this into account.

	.. note::

	      This routine need only be called for page cache pages
	      which can potentially ever be mapped into the address
	      space of a user process.  So for example, VFS layer code
	      handling vfs symlinks in the page cache need not call
	      this interface at all.

	The phrase "kernel writes to a page cache page" means, specifically,
	that the kernel executes store instructions that dirty data in that
	page at the page->virtual mapping of that page.  It is important to
	flush here to handle D-cache aliasing, to make sure these kernel stores
	are visible to user space mappings of that page.

	The corollary case is just as important, if there are users which have
	shared+writable mappings of this file, we must make sure that kernel
	reads of these pages will see the most recent stores done by the user.

	If D-cache aliasing is not an issue, this routine may simply be defined
	as a nop on that architecture.

        There is a bit set aside in page->flags (PG_arch_1) as "architecture
	private".  The kernel guarantees that, for pagecache pages, it will
	clear this bit when such a page first enters the pagecache.

	This allows these interfaces to be implemented much more efficiently.
	It allows one to "defer" (perhaps indefinitely) the actual flush if
	there are currently no user processes mapping this page.  See sparc64's
	flush_dcache_page and update_mmu_cache implementations for an example
	of how to go about doing this.

	The idea is, first at flush_dcache_page() time, if page_file_mapping()
	returns a mapping, and mapping_mapped on that mapping returns %false,
	just mark the architecture private page flag bit.  Later, in
	update_mmu_cache(), a check is made of this flag bit, and if set the
	flush is done and the flag bit is cleared.

	.. important::

			It is often important, if you defer the flush,
			that the actual flush occurs on the same CPU
			as did the cpu stores into the page to make it
			dirty.  Again, see sparc64 for examples of how
			to deal with this.

  ``void flush_dcache_folio(struct folio *folio)``
	This function is called under the same circumstances as
	flush_dcache_page().  It allows the architecture to
	optimise for flushing the entire folio of pages instead
	of flushing one page at a time.

  ``void copy_to_user_page(struct vm_area_struct *vma, struct page *page,
  unsigned long user_vaddr, void *dst, void *src, int len)``
  ``void copy_from_user_page(struct vm_area_struct *vma, struct page *page,
  unsigned long user_vaddr, void *dst, void *src, int len)``

	When the kernel needs to copy arbitrary data in and out
	of arbitrary user pages (f.e. for ptrace()) it will use
	these two routines.

	Any necessary cache flushing or other coherency operations
	that need to occur should happen here.  If the processor's
	instruction cache does not snoop cpu stores, it is very
	likely that you will need to flush the instruction cache
	for copy_to_user_page().

  ``void flush_anon_page(struct vm_area_struct *vma, struct page *page,
  unsigned long vmaddr)``

  	When the kernel needs to access the contents of an anonymous
	page, it calls this function (currently only
	get_user_pages()).  Note: flush_dcache_page() deliberately
	doesn't work for an anonymous page.  The default
	implementation is a nop (and should remain so for all coherent
	architectures).  For incoherent architectures, it should flush
	the cache of the page at vmaddr.

  ``void flush_icache_range(unsigned long start, unsigned long end)``

  	When the kernel stores into addresses that it will execute
	out of (eg when loading modules), this function is called.

	If the icache does not snoop stores then this routine will need
	to flush it.

  ``void flush_icache_page(struct vm_area_struct *vma, struct page *page)``

	All the functionality of flush_icache_page can be implemented in
	flush_dcache_page and update_mmu_cache. In the future, the hope
	is to remove this interface completely.

The final category of APIs is for I/O to deliberately aliased address
ranges inside the kernel.  Such aliases are set up by use of the
vmap/vmalloc API.  Since kernel I/O goes via physical pages, the I/O
subsystem assumes that the user mapping and kernel offset mapping are
the only aliases.  This isn't true for vmap aliases, so anything in
the kernel trying to do I/O to vmap areas must manually manage
coherency.  It must do this by flushing the vmap range before doing
I/O and invalidating it after the I/O returns.

  ``void flush_kernel_vmap_range(void *vaddr, int size)``

       flushes the kernel cache for a given virtual address range in
       the vmap area.  This is to make sure that any data the kernel
       modified in the vmap range is made visible to the physical
       page.  The design is to make this area safe to perform I/O on.
       Note that this API does *not* also flush the offset map alias
       of the area.

  ``void invalidate_kernel_vmap_range(void *vaddr, int size) invalidates``

       the cache for a given virtual address range in the vmap area
       which prevents the processor from making the cache stale by
       speculatively reading data while the I/O was occurring to the
       physical pages.  This is only necessary for data reads into the
       vmap area.


code:
================
Circular Buffers
================

:Author: David Howells <dhowells@redhat.com>
:Author: Paul E. McKenney <paulmck@linux.ibm.com>

Linux provides a number of features that can be used to implement circular
buffering.  There are two sets of such features:

 (1) Convenience functions for determining information about power-of-2 sized
     buffers.

 (2) Memory barriers for when the producer and the consumer of objects in the
     buffer don't want to share a lock.

To use these facilities, as discussed below, there needs to be just one
producer and just one consumer.  It is possible to handle multiple producers by
serialising them, and to handle multiple consumers by serialising them.

.. Contents:

 (*) What is a circular buffer?

 (*) Measuring power-of-2 buffers.

 (*) Using memory barriers with circular buffers.
     - The producer.
     - The consumer.

What is a circular buffer?
==========================

First of all, what is a circular buffer?  A circular buffer is a buffer of
fixed, finite size into which there are two indices:

 (1) A 'head' index - the point at which the producer inserts items into the
     buffer.

 (2) A 'tail' index - the point at which the consumer finds the next item in
     the buffer.

Typically when the tail pointer is equal to the head pointer, the buffer is
empty; and the buffer is full when the head pointer is one less than the tail
pointer.

The head index is incremented when items are added, and the tail index when
items are removed.  The tail index should never jump the head index, and both
indices should be wrapped to 0 when they reach the end of the buffer, thus
allowing an infinite amount of data to flow through the buffer.

Typically, items will all be of the same unit size, but this isn't strictly
required to use the techniques below.  The indices can be increased by more
than 1 if multiple items or variable-sized items are to be included in the
buffer, provided that neither index overtakes the other.  The implementer must
be careful, however, as a region more than one unit in size may wrap the end of
the buffer and be broken into two segments.

Measuring power-of-2 buffers
============================

Calculation of the occupancy or the remaining capacity of an arbitrarily sized
circular buffer would normally be a slow operation, requiring the use of a
modulus (divide) instruction.  However, if the buffer is of a power-of-2 size,
then a much quicker bitwise-AND instruction can be used instead.

Linux provides a set of macros for handling power-of-2 circular buffers.  These
can be made use of by::

	#include <linux/circ_buf.h>

The macros are:

 (#) Measure the remaining capacity of a buffer::

	CIRC_SPACE(head_index, tail_index, buffer_size);

     This returns the amount of space left in the buffer[1] into which items
     can be inserted.

 (#) Measure the maximum consecutive immediate space in a buffer::

	CIRC_SPACE_TO_END(head_index, tail_index, buffer_size);

     This returns the amount of consecutive space left in the buffer[1] into
     which items can be immediately inserted without having to wrap back to the
     beginning of the buffer.

 (#) Measure the occupancy of a buffer::

	CIRC_CNT(head_index, tail_index, buffer_size);

     This returns the number of items currently occupying a buffer[2].

 (#) Measure the non-wrapping occupancy of a buffer::

	CIRC_CNT_TO_END(head_index, tail_index, buffer_size);

     This returns the number of consecutive items[2] that can be extracted from
     the buffer without having to wrap back to the beginning of the buffer.

Each of these macros will nominally return a value between 0 and buffer_size-1,
however:

 (1) CIRC_SPACE*() are intended to be used in the producer.  To the producer
     they will return a lower bound as the producer controls the head index,
     but the consumer may still be depleting the buffer on another CPU and
     moving the tail index.

     To the consumer it will show an upper bound as the producer may be busy
     depleting the space.

 (2) CIRC_CNT*() are intended to be used in the consumer.  To the consumer they
     will return a lower bound as the consumer controls the tail index, but the
     producer may still be filling the buffer on another CPU and moving the
     head index.

     To the producer it will show an upper bound as the consumer may be busy
     emptying the buffer.

 (3) To a third party, the order in which the writes to the indices by the
     producer and consumer become visible cannot be guaranteed as they are
     independent and may be made on different CPUs - so the result in such a
     situation will merely be a guess, and may even be negative.

Using memory barriers with circular buffers
===========================================

By using memory barriers in conjunction with circular buffers, you can avoid
the need to:

 (1) use a single lock to govern access to both ends of the buffer, thus
     allowing the buffer to be filled and emptied at the same time; and

 (2) use atomic counter operations.

There are two sides to this: the producer that fills the buffer, and the
consumer that empties it.  Only one thing should be filling a buffer at any one
time, and only one thing should be emptying a buffer at any one time, but the
two sides can operate simultaneously.

The producer
------------

The producer will look something like this::

	spin_lock(&producer_lock);

	unsigned long head = buffer->head;
	/* The spin_unlock() and next spin_lock() provide needed ordering. */
	unsigned long tail = READ_ONCE(buffer->tail);

	if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
		/* insert one item into the buffer */
		struct item *item = buffer[head];

		produce_item(item);

		smp_store_release(buffer->head,
				  (head + 1) & (buffer->size - 1));

		/* wake_up() will make sure that the head is committed before
		 * waking anyone up */
		wake_up(consumer);
	}

	spin_unlock(&producer_lock);

This will instruct the CPU that the contents of the new item must be written
before the head index makes it available to the consumer and then instructs the
CPU that the revised head index must be written before the consumer is woken.

Note that wake_up() does not guarantee any sort of barrier unless something
is actually awakened.  We therefore cannot rely on it for ordering.  However,
there is always one element of the array left empty.  Therefore, the
producer must produce two elements before it could possibly corrupt the
element currently being read by the consumer.  Therefore, the unlock-lock
pair between consecutive invocations of the consumer provides the necessary
ordering between the read of the index indicating that the consumer has
vacated a given element and the write by the producer to that same element.

The Consumer
------------

The consumer will look something like this::

	spin_lock(&consumer_lock);

	/* Read index before reading contents at that index. */
	unsigned long head = smp_load_acquire(buffer->head);
	unsigned long tail = buffer->tail;

	if (CIRC_CNT(head, tail, buffer->size) >= 1) {

		/* extract one item from the buffer */
		struct item *item = buffer[tail];

		consume_item(item);

		/* Finish reading descriptor before incrementing tail. */
		smp_store_release(buffer->tail,
				  (tail + 1) & (buffer->size - 1));
	}

	spin_unlock(&consumer_lock);

This will instruct the CPU to make sure the index is up to date before reading
the new item, and then it shall make sure the CPU has finished reading the item
before it writes the new tail pointer, which will erase the item.

Note the use of READ_ONCE() and smp_load_acquire() to read the
opposition index.  This prevents the compiler from discarding and
reloading its cached value.  This isn't strictly needed if you can
be sure that the opposition index will _only_ be used the once.
The smp_load_acquire() additionally forces the CPU to order against
subsequent memory references.  Similarly, smp_store_release() is used
in both algorithms to write the thread's index.  This documents the
fact that we are writing to something that can be read concurrently,
prevents the compiler from tearing the store, and enforces ordering
against previous accesses.

Further reading
===============

See also Documentation/memory-barriers.txt for a description of Linux's memory
barrier facilities.


code:
=========================
CPU hotplug in the Kernel
=========================

:Date: September, 2021
:Author: Sebastian Andrzej Siewior <bigeasy@linutronix.de>,
         Rusty Russell <rusty@rustcorp.com.au>,
         Srivatsa Vaddagiri <vatsa@in.ibm.com>,
         Ashok Raj <ashok.raj@intel.com>,
         Joel Schopp <jschopp@austin.ibm.com>,
	 Thomas Gleixner <tglx@linutronix.de>

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

Modern advances in system architectures have introduced advanced error
reporting and correction capabilities in processors. There are couple OEMS that
support NUMA hardware which are hot pluggable as well, where physical node
insertion and removal require support for CPU hotplug.

Such advances require CPUs available to a kernel to be removed either for
provisioning reasons, or for RAS purposes to keep an offending CPU off
system execution path. Hence the need for CPU hotplug support in the
Linux kernel.

A more novel use of CPU-hotplug support is its use today in suspend resume
support for SMP. Dual-core and HT support makes even a laptop run SMP kernels
which didn't support these methods.

Command Line Switches
=====================
``maxcpus=n``
  Restrict boot time CPUs to *n*. Say if you have four CPUs, using
  ``maxcpus=2`` will only boot two. You can choose to bring the
  other CPUs later online.

``nr_cpus=n``
  Restrict the total amount of CPUs the kernel will support. If the number
  supplied here is lower than the number of physically available CPUs, then
  those CPUs can not be brought online later.

``additional_cpus=n``
  Use this to limit hotpluggable CPUs. This option sets
  ``cpu_possible_mask = cpu_present_mask + additional_cpus``

  This option is limited to the IA64 architecture.

``possible_cpus=n``
  This option sets ``possible_cpus`` bits in ``cpu_possible_mask``.

  This option is limited to the X86 and S390 architecture.

``cpu0_hotplug``
  Allow to shutdown CPU0.

  This option is limited to the X86 architecture.

CPU maps
========

``cpu_possible_mask``
  Bitmap of possible CPUs that can ever be available in the
  system. This is used to allocate some boot time memory for per_cpu variables
  that aren't designed to grow/shrink as CPUs are made available or removed.
  Once set during boot time discovery phase, the map is static, i.e no bits
  are added or removed anytime. Trimming it accurately for your system needs
  upfront can save some boot time memory.

``cpu_online_mask``
  Bitmap of all CPUs currently online. Its set in ``__cpu_up()``
  after a CPU is available for kernel scheduling and ready to receive
  interrupts from devices. Its cleared when a CPU is brought down using
  ``__cpu_disable()``, before which all OS services including interrupts are
  migrated to another target CPU.

``cpu_present_mask``
  Bitmap of CPUs currently present in the system. Not all
  of them may be online. When physical hotplug is processed by the relevant
  subsystem (e.g ACPI) can change and new bit either be added or removed
  from the map depending on the event is hot-add/hot-remove. There are currently
  no locking rules as of now. Typical usage is to init topology during boot,
  at which time hotplug is disabled.

You really don't need to manipulate any of the system CPU maps. They should
be read-only for most use. When setting up per-cpu resources almost always use
``cpu_possible_mask`` or ``for_each_possible_cpu()`` to iterate. To macro
``for_each_cpu()`` can be used to iterate over a custom CPU mask.

Never use anything other than ``cpumask_t`` to represent bitmap of CPUs.

Using CPU hotplug
=================

The kernel option *CONFIG_HOTPLUG_CPU* needs to be enabled. It is currently
available on multiple architectures including ARM, MIPS, PowerPC and X86. The
configuration is done via the sysfs interface::

 $ ls -lh /sys/devices/system/cpu
 total 0
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu0
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu1
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu2
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu3
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu4
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu5
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu6
 drwxr-xr-x  9 root root    0 Dec 21 16:33 cpu7
 drwxr-xr-x  2 root root    0 Dec 21 16:33 hotplug
 -r--r--r--  1 root root 4.0K Dec 21 16:33 offline
 -r--r--r--  1 root root 4.0K Dec 21 16:33 online
 -r--r--r--  1 root root 4.0K Dec 21 16:33 possible
 -r--r--r--  1 root root 4.0K Dec 21 16:33 present

The files *offline*, *online*, *possible*, *present* represent the CPU masks.
Each CPU folder contains an *online* file which controls the logical on (1) and
off (0) state. To logically shutdown CPU4::

 $ echo 0 > /sys/devices/system/cpu/cpu4/online
  smpboot: CPU 4 is now offline

Once the CPU is shutdown, it will be removed from */proc/interrupts*,
*/proc/cpuinfo* and should also not be shown visible by the *top* command. To
bring CPU4 back online::

 $ echo 1 > /sys/devices/system/cpu/cpu4/online
 smpboot: Booting Node 0 Processor 4 APIC 0x1

The CPU is usable again. This should work on all CPUs. CPU0 is often special
and excluded from CPU hotplug. On X86 the kernel option
*CONFIG_BOOTPARAM_HOTPLUG_CPU0* has to be enabled in order to be able to
shutdown CPU0. Alternatively the kernel command option *cpu0_hotplug* can be
used. Some known dependencies of CPU0:

* Resume from hibernate/suspend. Hibernate/suspend will fail if CPU0 is offline.
* PIC interrupts. CPU0 can't be removed if a PIC interrupt is detected.

Please let Fenghua Yu <fenghua.yu@intel.com> know if you find any dependencies
on CPU0.

The CPU hotplug coordination
============================

The offline case
----------------

Once a CPU has been logically shutdown the teardown callbacks of registered
hotplug states will be invoked, starting with ``CPUHP_ONLINE`` and terminating
at state ``CPUHP_OFFLINE``. This includes:

* If tasks are frozen due to a suspend operation then *cpuhp_tasks_frozen*
  will be set to true.
* All processes are migrated away from this outgoing CPU to new CPUs.
  The new CPU is chosen from each process' current cpuset, which may be
  a subset of all online CPUs.
* All interrupts targeted to this CPU are migrated to a new CPU
* timers are also migrated to a new CPU
* Once all services are migrated, kernel calls an arch specific routine
  ``__cpu_disable()`` to perform arch specific cleanup.

The CPU hotplug API
===================

CPU hotplug state machine
-------------------------

CPU hotplug uses a trivial state machine with a linear state space from
CPUHP_OFFLINE to CPUHP_ONLINE. Each state has a startup and a teardown
callback.

When a CPU is onlined, the startup callbacks are invoked sequentially until
the state CPUHP_ONLINE is reached. They can also be invoked when the
callbacks of a state are set up or an instance is added to a multi-instance
state.

When a CPU is offlined the teardown callbacks are invoked in the reverse
order sequentially until the state CPUHP_OFFLINE is reached. They can also
be invoked when the callbacks of a state are removed or an instance is
removed from a multi-instance state.

If a usage site requires only a callback in one direction of the hotplug
operations (CPU online or CPU offline) then the other not-required callback
can be set to NULL when the state is set up.

The state space is divided into three sections:

* The PREPARE section

  The PREPARE section covers the state space from CPUHP_OFFLINE to
  CPUHP_BRINGUP_CPU.

  The startup callbacks in this section are invoked before the CPU is
  started during a CPU online operation. The teardown callbacks are invoked
  after the CPU has become dysfunctional during a CPU offline operation.

  The callbacks are invoked on a control CPU as they can't obviously run on
  the hotplugged CPU which is either not yet started or has become
  dysfunctional already.

  The startup callbacks are used to setup resources which are required to
  bring a CPU successfully online. The teardown callbacks are used to free
  resources or to move pending work to an online CPU after the hotplugged
  CPU became dysfunctional.

  The startup callbacks are allowed to fail. If a callback fails, the CPU
  online operation is aborted and the CPU is brought down to the previous
  state (usually CPUHP_OFFLINE) again.

  The teardown callbacks in this section are not allowed to fail.

* The STARTING section

  The STARTING section covers the state space between CPUHP_BRINGUP_CPU + 1
  and CPUHP_AP_ONLINE.

  The startup callbacks in this section are invoked on the hotplugged CPU
  with interrupts disabled during a CPU online operation in the early CPU
  setup code. The teardown callbacks are invoked with interrupts disabled
  on the hotplugged CPU during a CPU offline operation shortly before the
  CPU is completely shut down.

  The callbacks in this section are not allowed to fail.

  The callbacks are used for low level hardware initialization/shutdown and
  for core subsystems.

* The ONLINE section

  The ONLINE section covers the state space between CPUHP_AP_ONLINE + 1 and
  CPUHP_ONLINE.

  The startup callbacks in this section are invoked on the hotplugged CPU
  during a CPU online operation. The teardown callbacks are invoked on the
  hotplugged CPU during a CPU offline operation.

  The callbacks are invoked in the context of the per CPU hotplug thread,
  which is pinned on the hotplugged CPU. The callbacks are invoked with
  interrupts and preemption enabled.

  The callbacks are allowed to fail. When a callback fails the hotplug
  operation is aborted and the CPU is brought back to the previous state.

CPU online/offline operations
-----------------------------

A successful online operation looks like this::

  [CPUHP_OFFLINE]
  [CPUHP_OFFLINE + 1]->startup()       -> success
  [CPUHP_OFFLINE + 2]->startup()       -> success
  [CPUHP_OFFLINE + 3]                  -> skipped because startup == NULL
  ...
  [CPUHP_BRINGUP_CPU]->startup()       -> success
  === End of PREPARE section
  [CPUHP_BRINGUP_CPU + 1]->startup()   -> success
  ...
  [CPUHP_AP_ONLINE]->startup()         -> success
  === End of STARTUP section
  [CPUHP_AP_ONLINE + 1]->startup()     -> success
  ...
  [CPUHP_ONLINE - 1]->startup()        -> success
  [CPUHP_ONLINE]

A successful offline operation looks like this::

  [CPUHP_ONLINE]
  [CPUHP_ONLINE - 1]->teardown()       -> success
  ...
  [CPUHP_AP_ONLINE + 1]->teardown()    -> success
  === Start of STARTUP section
  [CPUHP_AP_ONLINE]->teardown()        -> success
  ...
  [CPUHP_BRINGUP_ONLINE - 1]->teardown()
  ...
  === Start of PREPARE section
  [CPUHP_BRINGUP_CPU]->teardown()
  [CPUHP_OFFLINE + 3]->teardown()
  [CPUHP_OFFLINE + 2]                  -> skipped because teardown == NULL
  [CPUHP_OFFLINE + 1]->teardown()
  [CPUHP_OFFLINE]

A failed online operation looks like this::

  [CPUHP_OFFLINE]
  [CPUHP_OFFLINE + 1]->startup()       -> success
  [CPUHP_OFFLINE + 2]->startup()       -> success
  [CPUHP_OFFLINE + 3]                  -> skipped because startup == NULL
  ...
  [CPUHP_BRINGUP_CPU]->startup()       -> success
  === End of PREPARE section
  [CPUHP_BRINGUP_CPU + 1]->startup()   -> success
  ...
  [CPUHP_AP_ONLINE]->startup()         -> success
  === End of STARTUP section
  [CPUHP_AP_ONLINE + 1]->startup()     -> success
  ---
  [CPUHP_AP_ONLINE + N]->startup()     -> fail
  [CPUHP_AP_ONLINE + (N - 1)]->teardown()
  ...
  [CPUHP_AP_ONLINE + 1]->teardown()
  === Start of STARTUP section
  [CPUHP_AP_ONLINE]->teardown()
  ...
  [CPUHP_BRINGUP_ONLINE - 1]->teardown()
  ...
  === Start of PREPARE section
  [CPUHP_BRINGUP_CPU]->teardown()
  [CPUHP_OFFLINE + 3]->teardown()
  [CPUHP_OFFLINE + 2]                  -> skipped because teardown == NULL
  [CPUHP_OFFLINE + 1]->teardown()
  [CPUHP_OFFLINE]

A failed offline operation looks like this::

  [CPUHP_ONLINE]
  [CPUHP_ONLINE - 1]->teardown()       -> success
  ...
  [CPUHP_ONLINE - N]->teardown()       -> fail
  [CPUHP_ONLINE - (N - 1)]->startup()
  ...
  [CPUHP_ONLINE - 1]->startup()
  [CPUHP_ONLINE]

Recursive failures cannot be handled sensibly. Look at the following
example of a recursive fail due to a failed offline operation: ::

  [CPUHP_ONLINE]
  [CPUHP_ONLINE - 1]->teardown()       -> success
  ...
  [CPUHP_ONLINE - N]->teardown()       -> fail
  [CPUHP_ONLINE - (N - 1)]->startup()  -> success
  [CPUHP_ONLINE - (N - 2)]->startup()  -> fail

The CPU hotplug state machine stops right here and does not try to go back
down again because that would likely result in an endless loop::

  [CPUHP_ONLINE - (N - 1)]->teardown() -> success
  [CPUHP_ONLINE - N]->teardown()       -> fail
  [CPUHP_ONLINE - (N - 1)]->startup()  -> success
  [CPUHP_ONLINE - (N - 2)]->startup()  -> fail
  [CPUHP_ONLINE - (N - 1)]->teardown() -> success
  [CPUHP_ONLINE - N]->teardown()       -> fail

Lather, rinse and repeat. In this case the CPU left in state::

  [CPUHP_ONLINE - (N - 1)]

which at least lets the system make progress and gives the user a chance to
debug or even resolve the situation.

Allocating a state
------------------

There are two ways to allocate a CPU hotplug state:

* Static allocation

  Static allocation has to be used when the subsystem or driver has
  ordering requirements versus other CPU hotplug states. E.g. the PERF core
  startup callback has to be invoked before the PERF driver startup
  callbacks during a CPU online operation. During a CPU offline operation
  the driver teardown callbacks have to be invoked before the core teardown
  callback. The statically allocated states are described by constants in
  the cpuhp_state enum which can be found in include/linux/cpuhotplug.h.

  Insert the state into the enum at the proper place so the ordering
  requirements are fulfilled. The state constant has to be used for state
  setup and removal.

  Static allocation is also required when the state callbacks are not set
  up at runtime and are part of the initializer of the CPU hotplug state
  array in kernel/cpu.c.

* Dynamic allocation

  When there are no ordering requirements for the state callbacks then
  dynamic allocation is the preferred method. The state number is allocated
  by the setup function and returned to the caller on success.

  Only the PREPARE and ONLINE sections provide a dynamic allocation
  range. The STARTING section does not as most of the callbacks in that
  section have explicit ordering requirements.

Setup of a CPU hotplug state
----------------------------

The core code provides the following functions to setup a state:

* cpuhp_setup_state(state, name, startup, teardown)
* cpuhp_setup_state_nocalls(state, name, startup, teardown)
* cpuhp_setup_state_cpuslocked(state, name, startup, teardown)
* cpuhp_setup_state_nocalls_cpuslocked(state, name, startup, teardown)

For cases where a driver or a subsystem has multiple instances and the same
CPU hotplug state callbacks need to be invoked for each instance, the CPU
hotplug core provides multi-instance support. The advantage over driver
specific instance lists is that the instance related functions are fully
serialized against CPU hotplug operations and provide the automatic
invocations of the state callbacks on add and removal. To set up such a
multi-instance state the following function is available:

* cpuhp_setup_state_multi(state, name, startup, teardown)

The @state argument is either a statically allocated state or one of the
constants for dynamically allocated states - CPUHP_PREPARE_DYN,
CPUHP_ONLINE_DYN - depending on the state section (PREPARE, ONLINE) for
which a dynamic state should be allocated.

The @name argument is used for sysfs output and for instrumentation. The
naming convention is "subsys:mode" or "subsys/driver:mode",
e.g. "perf:mode" or "perf/x86:mode". The common mode names are:

======== =======================================================
prepare  For states in the PREPARE section

dead     For states in the PREPARE section which do not provide
         a startup callback

starting For states in the STARTING section

dying    For states in the STARTING section which do not provide
         a startup callback

online   For states in the ONLINE section

offline  For states in the ONLINE section which do not provide
         a startup callback
======== =======================================================

As the @name argument is only used for sysfs and instrumentation other mode
descriptors can be used as well if they describe the nature of the state
better than the common ones.

Examples for @name arguments: "perf/online", "perf/x86:prepare",
"RCU/tree:dying", "sched/waitempty"

The @startup argument is a function pointer to the callback which should be
invoked during a CPU online operation. If the usage site does not require a
startup callback set the pointer to NULL.

The @teardown argument is a function pointer to the callback which should
be invoked during a CPU offline operation. If the usage site does not
require a teardown callback set the pointer to NULL.

The functions differ in the way how the installed callbacks are treated:

  * cpuhp_setup_state_nocalls(), cpuhp_setup_state_nocalls_cpuslocked()
    and cpuhp_setup_state_multi() only install the callbacks

  * cpuhp_setup_state() and cpuhp_setup_state_cpuslocked() install the
    callbacks and invoke the @startup callback (if not NULL) for all online
    CPUs which have currently a state greater than the newly installed
    state. Depending on the state section the callback is either invoked on
    the current CPU (PREPARE section) or on each online CPU (ONLINE
    section) in the context of the CPU's hotplug thread.

    If a callback fails for CPU N then the teardown callback for CPU
    0 .. N-1 is invoked to rollback the operation. The state setup fails,
    the callbacks for the state are not installed and in case of dynamic
    allocation the allocated state is freed.

The state setup and the callback invocations are serialized against CPU
hotplug operations. If the setup function has to be called from a CPU
hotplug read locked region, then the _cpuslocked() variants have to be
used. These functions cannot be used from within CPU hotplug callbacks.

The function return values:
  ======== ===================================================================
  0        Statically allocated state was successfully set up

  >0       Dynamically allocated state was successfully set up.

           The returned number is the state number which was allocated. If
           the state callbacks have to be removed later, e.g. module
           removal, then this number has to be saved by the caller and used
           as @state argument for the state remove function. For
           multi-instance states the dynamically allocated state number is
           also required as @state argument for the instance add/remove
           operations.

  <0	   Operation failed
  ======== ===================================================================

Removal of a CPU hotplug state
------------------------------

To remove a previously set up state, the following functions are provided:

* cpuhp_remove_state(state)
* cpuhp_remove_state_nocalls(state)
* cpuhp_remove_state_nocalls_cpuslocked(state)
* cpuhp_remove_multi_state(state)

The @state argument is either a statically allocated state or the state
number which was allocated in the dynamic range by cpuhp_setup_state*(). If
the state is in the dynamic range, then the state number is freed and
available for dynamic allocation again.

The functions differ in the way how the installed callbacks are treated:

  * cpuhp_remove_state_nocalls(), cpuhp_remove_state_nocalls_cpuslocked()
    and cpuhp_remove_multi_state() only remove the callbacks.

  * cpuhp_remove_state() removes the callbacks and invokes the teardown
    callback (if not NULL) for all online CPUs which have currently a state
    greater than the removed state. Depending on the state section the
    callback is either invoked on the current CPU (PREPARE section) or on
    each online CPU (ONLINE section) in the context of the CPU's hotplug
    thread.

    In order to complete the removal, the teardown callback should not fail.

The state removal and the callback invocations are serialized against CPU
hotplug operations. If the remove function has to be called from a CPU
hotplug read locked region, then the _cpuslocked() variants have to be
used. These functions cannot be used from within CPU hotplug callbacks.

If a multi-instance state is removed then the caller has to remove all
instances first.

Multi-Instance state instance management
----------------------------------------

Once the multi-instance state is set up, instances can be added to the
state:

  * cpuhp_state_add_instance(state, node)
  * cpuhp_state_add_instance_nocalls(state, node)

The @state argument is either a statically allocated state or the state
number which was allocated in the dynamic range by cpuhp_setup_state_multi().

The @node argument is a pointer to an hlist_node which is embedded in the
instance's data structure. The pointer is handed to the multi-instance
state callbacks and can be used by the callback to retrieve the instance
via container_of().

The functions differ in the way how the installed callbacks are treated:

  * cpuhp_state_add_instance_nocalls() and only adds the instance to the
    multi-instance state's node list.

  * cpuhp_state_add_instance() adds the instance and invokes the startup
    callback (if not NULL) associated with @state for all online CPUs which
    have currently a state greater than @state. The callback is only
    invoked for the to be added instance. Depending on the state section
    the callback is either invoked on the current CPU (PREPARE section) or
    on each online CPU (ONLINE section) in the context of the CPU's hotplug
    thread.

    If a callback fails for CPU N then the teardown callback for CPU
    0 .. N-1 is invoked to rollback the operation, the function fails and
    the instance is not added to the node list of the multi-instance state.

To remove an instance from the state's node list these functions are
available:

  * cpuhp_state_remove_instance(state, node)
  * cpuhp_state_remove_instance_nocalls(state, node)

The arguments are the same as for the cpuhp_state_add_instance*()
variants above.

The functions differ in the way how the installed callbacks are treated:

  * cpuhp_state_remove_instance_nocalls() only removes the instance from the
    state's node list.

  * cpuhp_state_remove_instance() removes the instance and invokes the
    teardown callback (if not NULL) associated with @state for all online
    CPUs which have currently a state greater than @state.  The callback is
    only invoked for the to be removed instance.  Depending on the state
    section the callback is either invoked on the current CPU (PREPARE
    section) or on each online CPU (ONLINE section) in the context of the
    CPU's hotplug thread.

    In order to complete the removal, the teardown callback should not fail.

The node list add/remove operations and the callback invocations are
serialized against CPU hotplug operations. These functions cannot be used
from within CPU hotplug callbacks and CPU hotplug read locked regions.

Examples
--------

Setup and teardown a statically allocated state in the STARTING section for
notifications on online and offline operations::

   ret = cpuhp_setup_state(CPUHP_SUBSYS_STARTING, "subsys:starting", subsys_cpu_starting, subsys_cpu_dying);
   if (ret < 0)
        return ret;
   ....
   cpuhp_remove_state(CPUHP_SUBSYS_STARTING);

Setup and teardown a dynamically allocated state in the ONLINE section
for notifications on offline operations::

   state = cpuhp_setup_state(CPUHP_ONLINE_DYN, "subsys:offline", NULL, subsys_cpu_offline);
   if (state < 0)
       return state;
   ....
   cpuhp_remove_state(state);

Setup and teardown a dynamically allocated state in the ONLINE section
for notifications on online operations without invoking the callbacks::

   state = cpuhp_setup_state_nocalls(CPUHP_ONLINE_DYN, "subsys:online", subsys_cpu_online, NULL);
   if (state < 0)
       return state;
   ....
   cpuhp_remove_state_nocalls(state);

Setup, use and teardown a dynamically allocated multi-instance state in the
ONLINE section for notifications on online and offline operation::

   state = cpuhp_setup_state_multi(CPUHP_ONLINE_DYN, "subsys:online", subsys_cpu_online, subsys_cpu_offline);
   if (state < 0)
       return state;
   ....
   ret = cpuhp_state_add_instance(state, &inst1->node);
   if (ret)
        return ret;
   ....
   ret = cpuhp_state_add_instance(state, &inst2->node);
   if (ret)
        return ret;
   ....
   cpuhp_remove_instance(state, &inst1->node);
   ....
   cpuhp_remove_instance(state, &inst2->node);
   ....
   remove_multi_state(state);

Testing of hotplug states
=========================

One way to verify whether a custom state is working as expected or not is to
shutdown a CPU and then put it online again. It is also possible to put the CPU
to certain state (for instance *CPUHP_AP_ONLINE*) and then go back to
*CPUHP_ONLINE*. This would simulate an error one state after *CPUHP_AP_ONLINE*
which would lead to rollback to the online state.

All registered states are enumerated in ``/sys/devices/system/cpu/hotplug/states`` ::

 $ tail /sys/devices/system/cpu/hotplug/states
 138: mm/vmscan:online
 139: mm/vmstat:online
 140: lib/percpu_cnt:online
 141: acpi/cpu-drv:online
 142: base/cacheinfo:online
 143: virtio/net:online
 144: x86/mce:online
 145: printk:online
 168: sched:active
 169: online

To rollback CPU4 to ``lib/percpu_cnt:online`` and back online just issue::

  $ cat /sys/devices/system/cpu/cpu4/hotplug/state
  169
  $ echo 140 > /sys/devices/system/cpu/cpu4/hotplug/target
  $ cat /sys/devices/system/cpu/cpu4/hotplug/state
  140

It is important to note that the teardown callback of state 140 have been
invoked. And now get back online::

  $ echo 169 > /sys/devices/system/cpu/cpu4/hotplug/target
  $ cat /sys/devices/system/cpu/cpu4/hotplug/state
  169

With trace events enabled, the individual steps are visible, too::

  #  TASK-PID   CPU#    TIMESTAMP  FUNCTION
  #     | |       |        |         |
      bash-394  [001]  22.976: cpuhp_enter: cpu: 0004 target: 140 step: 169 (cpuhp_kick_ap_work)
   cpuhp/4-31   [004]  22.977: cpuhp_enter: cpu: 0004 target: 140 step: 168 (sched_cpu_deactivate)
   cpuhp/4-31   [004]  22.990: cpuhp_exit:  cpu: 0004  state: 168 step: 168 ret: 0
   cpuhp/4-31   [004]  22.991: cpuhp_enter: cpu: 0004 target: 140 step: 144 (mce_cpu_pre_down)
   cpuhp/4-31   [004]  22.992: cpuhp_exit:  cpu: 0004  state: 144 step: 144 ret: 0
   cpuhp/4-31   [004]  22.993: cpuhp_multi_enter: cpu: 0004 target: 140 step: 143 (virtnet_cpu_down_prep)
   cpuhp/4-31   [004]  22.994: cpuhp_exit:  cpu: 0004  state: 143 step: 143 ret: 0
   cpuhp/4-31   [004]  22.995: cpuhp_enter: cpu: 0004 target: 140 step: 142 (cacheinfo_cpu_pre_down)
   cpuhp/4-31   [004]  22.996: cpuhp_exit:  cpu: 0004  state: 142 step: 142 ret: 0
      bash-394  [001]  22.997: cpuhp_exit:  cpu: 0004  state: 140 step: 169 ret: 0
      bash-394  [005]  95.540: cpuhp_enter: cpu: 0004 target: 169 step: 140 (cpuhp_kick_ap_work)
   cpuhp/4-31   [004]  95.541: cpuhp_enter: cpu: 0004 target: 169 step: 141 (acpi_soft_cpu_online)
   cpuhp/4-31   [004]  95.542: cpuhp_exit:  cpu: 0004  state: 141 step: 141 ret: 0
   cpuhp/4-31   [004]  95.543: cpuhp_enter: cpu: 0004 target: 169 step: 142 (cacheinfo_cpu_online)
   cpuhp/4-31   [004]  95.544: cpuhp_exit:  cpu: 0004  state: 142 step: 142 ret: 0
   cpuhp/4-31   [004]  95.545: cpuhp_multi_enter: cpu: 0004 target: 169 step: 143 (virtnet_cpu_online)
   cpuhp/4-31   [004]  95.546: cpuhp_exit:  cpu: 0004  state: 143 step: 143 ret: 0
   cpuhp/4-31   [004]  95.547: cpuhp_enter: cpu: 0004 target: 169 step: 144 (mce_cpu_online)
   cpuhp/4-31   [004]  95.548: cpuhp_exit:  cpu: 0004  state: 144 step: 144 ret: 0
   cpuhp/4-31   [004]  95.549: cpuhp_enter: cpu: 0004 target: 169 step: 145 (console_cpu_notify)
   cpuhp/4-31   [004]  95.550: cpuhp_exit:  cpu: 0004  state: 145 step: 145 ret: 0
   cpuhp/4-31   [004]  95.551: cpuhp_enter: cpu: 0004 target: 169 step: 168 (sched_cpu_activate)
   cpuhp/4-31   [004]  95.552: cpuhp_exit:  cpu: 0004  state: 168 step: 168 ret: 0
      bash-394  [005]  95.553: cpuhp_exit:  cpu: 0004  state: 169 step: 140 ret: 0

As it an be seen, CPU4 went down until timestamp 22.996 and then back up until
95.552. All invoked callbacks including their return codes are visible in the
trace.

Architecture's requirements
===========================

The following functions and configurations are required:

``CONFIG_HOTPLUG_CPU``
  This entry needs to be enabled in Kconfig

``__cpu_up()``
  Arch interface to bring up a CPU

``__cpu_disable()``
  Arch interface to shutdown a CPU, no more interrupts can be handled by the
  kernel after the routine returns. This includes the shutdown of the timer.

``__cpu_die()``
  This actually supposed to ensure death of the CPU. Actually look at some
  example code in other arch that implement CPU hotplug. The processor is taken
  down from the ``idle()`` loop for that specific architecture. ``__cpu_die()``
  typically waits for some per_cpu state to be set, to ensure the processor dead
  routine is called to be sure positively.

User Space Notification
=======================

After CPU successfully onlined or offline udev events are sent. A udev rule like::

  SUBSYSTEM=="cpu", DRIVERS=="processor", DEVPATH=="/devices/system/cpu/*", RUN+="the_hotplug_receiver.sh"

will receive all events. A script like::

  #!/bin/sh

  if [ "${ACTION}" = "offline" ]
  then
      echo "CPU ${DEVPATH##*/} offline"

  elif [ "${ACTION}" = "online" ]
  then
      echo "CPU ${DEVPATH##*/} online"

  fi

can process the event further.

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

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


code:
============================================
The object-lifetime debugging infrastructure
============================================

:Author: Thomas Gleixner

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

debugobjects is a generic infrastructure to track the life time of
kernel objects and validate the operations on those.

debugobjects is useful to check for the following error patterns:

-  Activation of uninitialized objects

-  Initialization of active objects

-  Usage of freed/destroyed objects

debugobjects is not changing the data structure of the real object so it
can be compiled in with a minimal runtime impact and enabled on demand
with a kernel command line option.

Howto use debugobjects
======================

A kernel subsystem needs to provide a data structure which describes the
object type and add calls into the debug code at appropriate places. The
data structure to describe the object type needs at minimum the name of
the object type. Optional functions can and should be provided to fixup
detected problems so the kernel can continue to work and the debug
information can be retrieved from a live system instead of hard core
debugging with serial consoles and stack trace transcripts from the
monitor.

The debug calls provided by debugobjects are:

-  debug_object_init

-  debug_object_init_on_stack

-  debug_object_activate

-  debug_object_deactivate

-  debug_object_destroy

-  debug_object_free

-  debug_object_assert_init

Each of these functions takes the address of the real object and a
pointer to the object type specific debug description structure.

Each detected error is reported in the statistics and a limited number
of errors are printk'ed including a full stack trace.

The statistics are available via /sys/kernel/debug/debug_objects/stats.
They provide information about the number of warnings and the number of
successful fixups along with information about the usage of the internal
tracking objects and the state of the internal tracking objects pool.

Debug functions
===============

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_init

This function is called whenever the initialization function of a real
object is called.

When the real object is already tracked by debugobjects it is checked,
whether the object can be initialized. Initializing is not allowed for
active and destroyed objects. When debugobjects detects an error, then
it calls the fixup_init function of the object type description
structure if provided by the caller. The fixup function can correct the
problem before the real initialization of the object happens. E.g. it
can deactivate an active object in order to prevent damage to the
subsystem.

When the real object is not yet tracked by debugobjects, debugobjects
allocates a tracker object for the real object and sets the tracker
object state to ODEBUG_STATE_INIT. It verifies that the object is not
on the callers stack. If it is on the callers stack then a limited
number of warnings including a full stack trace is printk'ed. The
calling code must use debug_object_init_on_stack() and remove the
object before leaving the function which allocated it. See next section.

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_init_on_stack

This function is called whenever the initialization function of a real
object which resides on the stack is called.

When the real object is already tracked by debugobjects it is checked,
whether the object can be initialized. Initializing is not allowed for
active and destroyed objects. When debugobjects detects an error, then
it calls the fixup_init function of the object type description
structure if provided by the caller. The fixup function can correct the
problem before the real initialization of the object happens. E.g. it
can deactivate an active object in order to prevent damage to the
subsystem.

When the real object is not yet tracked by debugobjects debugobjects
allocates a tracker object for the real object and sets the tracker
object state to ODEBUG_STATE_INIT. It verifies that the object is on
the callers stack.

An object which is on the stack must be removed from the tracker by
calling debug_object_free() before the function which allocates the
object returns. Otherwise we keep track of stale objects.

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_activate

This function is called whenever the activation function of a real
object is called.

When the real object is already tracked by debugobjects it is checked,
whether the object can be activated. Activating is not allowed for
active and destroyed objects. When debugobjects detects an error, then
it calls the fixup_activate function of the object type description
structure if provided by the caller. The fixup function can correct the
problem before the real activation of the object happens. E.g. it can
deactivate an active object in order to prevent damage to the subsystem.

When the real object is not yet tracked by debugobjects then the
fixup_activate function is called if available. This is necessary to
allow the legitimate activation of statically allocated and initialized
objects. The fixup function checks whether the object is valid and calls
the debug_objects_init() function to initialize the tracking of this
object.

When the activation is legitimate, then the state of the associated
tracker object is set to ODEBUG_STATE_ACTIVE.

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_deactivate

This function is called whenever the deactivation function of a real
object is called.

When the real object is tracked by debugobjects it is checked, whether
the object can be deactivated. Deactivating is not allowed for untracked
or destroyed objects.

When the deactivation is legitimate, then the state of the associated
tracker object is set to ODEBUG_STATE_INACTIVE.

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_destroy

This function is called to mark an object destroyed. This is useful to
prevent the usage of invalid objects, which are still available in
memory: either statically allocated objects or objects which are freed
later.

When the real object is tracked by debugobjects it is checked, whether
the object can be destroyed. Destruction is not allowed for active and
destroyed objects. When debugobjects detects an error, then it calls the
fixup_destroy function of the object type description structure if
provided by the caller. The fixup function can correct the problem
before the real destruction of the object happens. E.g. it can
deactivate an active object in order to prevent damage to the subsystem.

When the destruction is legitimate, then the state of the associated
tracker object is set to ODEBUG_STATE_DESTROYED.

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_free

This function is called before an object is freed.

When the real object is tracked by debugobjects it is checked, whether
the object can be freed. Free is not allowed for active objects. When
debugobjects detects an error, then it calls the fixup_free function of
the object type description structure if provided by the caller. The
fixup function can correct the problem before the real free of the
object happens. E.g. it can deactivate an active object in order to
prevent damage to the subsystem.

Note that debug_object_free removes the object from the tracker. Later
usage of the object is detected by the other debug checks.

.. kernel-doc:: lib/debugobjects.c
   :functions: debug_object_assert_init

This function is called to assert that an object has been initialized.

When the real object is not tracked by debugobjects, it calls
fixup_assert_init of the object type description structure provided by
the caller, with the hardcoded object state ODEBUG_NOT_AVAILABLE. The
fixup function can correct the problem by calling debug_object_init
and other specific initializing functions.

When the real object is already tracked by debugobjects it is ignored.

Fixup functions
===============

Debug object type description structure
---------------------------------------

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

fixup_init
-----------

This function is called from the debug code whenever a problem in
debug_object_init is detected. The function takes the address of the
object and the state which is currently recorded in the tracker.

Called from debug_object_init when the object state is:

-  ODEBUG_STATE_ACTIVE

The function returns true when the fixup was successful, otherwise
false. The return value is used to update the statistics.

Note, that the function needs to call the debug_object_init() function
again, after the damage has been repaired in order to keep the state
consistent.

fixup_activate
---------------

This function is called from the debug code whenever a problem in
debug_object_activate is detected.

Called from debug_object_activate when the object state is:

-  ODEBUG_STATE_NOTAVAILABLE

-  ODEBUG_STATE_ACTIVE

The function returns true when the fixup was successful, otherwise
false. The return value is used to update the statistics.

Note that the function needs to call the debug_object_activate()
function again after the damage has been repaired in order to keep the
state consistent.

The activation of statically initialized objects is a special case. When
debug_object_activate() has no tracked object for this object address
then fixup_activate() is called with object state
ODEBUG_STATE_NOTAVAILABLE. The fixup function needs to check whether
this is a legitimate case of a statically initialized object or not. In
case it is it calls debug_object_init() and debug_object_activate()
to make the object known to the tracker and marked active. In this case
the function should return false because this is not a real fixup.

fixup_destroy
--------------

This function is called from the debug code whenever a problem in
debug_object_destroy is detected.

Called from debug_object_destroy when the object state is:

-  ODEBUG_STATE_ACTIVE

The function returns true when the fixup was successful, otherwise
false. The return value is used to update the statistics.

fixup_free
-----------

This function is called from the debug code whenever a problem in
debug_object_free is detected. Further it can be called from the debug
checks in kfree/vfree, when an active object is detected from the
debug_check_no_obj_freed() sanity checks.

Called from debug_object_free() or debug_check_no_obj_freed() when
the object state is:

-  ODEBUG_STATE_ACTIVE

The function returns true when the fixup was successful, otherwise
false. The return value is used to update the statistics.

fixup_assert_init
-------------------

This function is called from the debug code whenever a problem in
debug_object_assert_init is detected.

Called from debug_object_assert_init() with a hardcoded state
ODEBUG_STATE_NOTAVAILABLE when the object is not found in the debug
bucket.

The function returns true when the fixup was successful, otherwise
false. The return value is used to update the statistics.

Note, this function should make sure debug_object_init() is called
before returning.

The handling of statically initialized objects is a special case. The
fixup function should check if this is a legitimate case of a statically
initialized object or not. In this case only debug_object_init()
should be called to make the object known to the tracker. Then the
function should return false because this is not a real fixup.

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

None (knock on wood).


code:
===========================================================================
Using physical DMA provided by OHCI-1394 FireWire controllers for debugging
===========================================================================

Introduction
------------

Basically all FireWire controllers which are in use today are compliant
to the OHCI-1394 specification which defines the controller to be a PCI
bus master which uses DMA to offload data transfers from the CPU and has
a "Physical Response Unit" which executes specific requests by employing
PCI-Bus master DMA after applying filters defined by the OHCI-1394 driver.

Once properly configured, remote machines can send these requests to
ask the OHCI-1394 controller to perform read and write requests on
physical system memory and, for read requests, send the result of
the physical memory read back to the requester.

With that, it is possible to debug issues by reading interesting memory
locations such as buffers like the printk buffer or the process table.

Retrieving a full system memory dump is also possible over the FireWire,
using data transfer rates in the order of 10MB/s or more.

With most FireWire controllers, memory access is limited to the low 4 GB
of physical address space.  This can be a problem on IA64 machines where
memory is located mostly above that limit, but it is rarely a problem on
more common hardware such as x86, x86-64 and PowerPC.

At least LSI FW643e and FW643e2 controllers are known to support access to
physical addresses above 4 GB, but this feature is currently not enabled by
Linux.

Together with a early initialization of the OHCI-1394 controller for debugging,
this facility proved most useful for examining long debugs logs in the printk
buffer on to debug early boot problems in areas like ACPI where the system
fails to boot and other means for debugging (serial port) are either not
available (notebooks) or too slow for extensive debug information (like ACPI).

Drivers
-------

The firewire-ohci driver in drivers/firewire uses filtered physical
DMA by default, which is more secure but not suitable for remote debugging.
Pass the remote_dma=1 parameter to the driver to get unfiltered physical DMA.

Because the firewire-ohci driver depends on the PCI enumeration to be
completed, an initialization routine which runs pretty early has been
implemented for x86.  This routine runs long before console_init() can be
called, i.e. before the printk buffer appears on the console.

To activate it, enable CONFIG_PROVIDE_OHCI1394_DMA_INIT (Kernel hacking menu:
Remote debugging over FireWire early on boot) and pass the parameter
"ohci1394_dma=early" to the recompiled kernel on boot.

Tools
-----

firescope - Originally developed by Benjamin Herrenschmidt, Andi Kleen ported
it from PowerPC to x86 and x86_64 and added functionality, firescope can now
be used to view the printk buffer of a remote machine, even with live update.

Bernhard Kaindl enhanced firescope to support accessing 64-bit machines
from 32-bit firescope and vice versa:
- http://v3.sk/~lkundrak/firescope/

and he implemented fast system dump (alpha version - read README.txt):
- http://halobates.de/firewire/firedump-0.1.tar.bz2

There is also a gdb proxy for firewire which allows to use gdb to access
data which can be referenced from symbols found by gdb in vmlinux:
- http://halobates.de/firewire/fireproxy-0.33.tar.bz2

The latest version of this gdb proxy (fireproxy-0.34) can communicate (not
yet stable) with kgdb over an memory-based communication module (kgdbom).

Getting Started
---------------

The OHCI-1394 specification regulates that the OHCI-1394 controller must
disable all physical DMA on each bus reset.

This means that if you want to debug an issue in a system state where
interrupts are disabled and where no polling of the OHCI-1394 controller
for bus resets takes place, you have to establish any FireWire cable
connections and fully initialize all FireWire hardware __before__ the
system enters such state.

Step-by-step instructions for using firescope with early OHCI initialization:

1) Verify that your hardware is supported:

   Load the firewire-ohci module and check your kernel logs.
   You should see a line similar to::

     firewire_ohci 0000:15:00.1: added OHCI v1.0 device as card 2, 4 IR + 4 IT
     ... contexts, quirks 0x11

   when loading the driver. If you have no supported controller, many PCI,
   CardBus and even some Express cards which are fully compliant to OHCI-1394
   specification are available. If it requires no driver for Windows operating
   systems, it most likely is. Only specialized shops have cards which are not
   compliant, they are based on TI PCILynx chips and require drivers for Windows
   operating systems.

   The mentioned kernel log message contains the string "physUB" if the
   controller implements a writable Physical Upper Bound register.  This is
   required for physical DMA above 4 GB (but not utilized by Linux yet).

2) Establish a working FireWire cable connection:

   Any FireWire cable, as long at it provides electrically and mechanically
   stable connection and has matching connectors (there are small 4-pin and
   large 6-pin FireWire ports) will do.

   If an driver is running on both machines you should see a line like::

     firewire_core 0000:15:00.1: created device fw1: GUID 00061b0020105917, S400

   on both machines in the kernel log when the cable is plugged in
   and connects the two machines.

3) Test physical DMA using firescope:

   On the debug host, make sure that /dev/fw* is accessible,
   then start firescope::

	$ firescope
	Port 0 (/dev/fw1) opened, 2 nodes detected

	FireScope
	---------
	Target : <unspecified>
	Gen    : 1
	[Ctrl-T] choose target
	[Ctrl-H] this menu
	[Ctrl-Q] quit

    ------> Press Ctrl-T now, the output should be similar to:

	2 nodes available, local node is: 0
	 0: ffc0, uuid: 00000000 00000000 [LOCAL]
	 1: ffc1, uuid: 00279000 ba4bb801

   Besides the [LOCAL] node, it must show another node without error message.

4) Prepare for debugging with early OHCI-1394 initialization:

   4.1) Kernel compilation and installation on debug target

   Compile the kernel to be debugged with CONFIG_PROVIDE_OHCI1394_DMA_INIT
   (Kernel hacking: Provide code for enabling DMA over FireWire early on boot)
   enabled and install it on the machine to be debugged (debug target).

   4.2) Transfer the System.map of the debugged kernel to the debug host

   Copy the System.map of the kernel be debugged to the debug host (the host
   which is connected to the debugged machine over the FireWire cable).

5) Retrieving the printk buffer contents:

   With the FireWire cable connected, the OHCI-1394 driver on the debugging
   host loaded, reboot the debugged machine, booting the kernel which has
   CONFIG_PROVIDE_OHCI1394_DMA_INIT enabled, with the option ohci1394_dma=early.

   Then, on the debugging host, run firescope, for example by using -A::

	firescope -A System.map-of-debug-target-kernel

   Note: -A automatically attaches to the first non-local node. It only works
   reliably if only connected two machines are connected using FireWire.

   After having attached to the debug target, press Ctrl-D to view the
   complete printk buffer or Ctrl-U to enter auto update mode and get an
   updated live view of recent kernel messages logged on the debug target.

   Call "firescope -h" to get more information on firescope's options.

Notes
-----

Documentation and specifications: http://halobates.de/firewire/

FireWire is a trademark of Apple Inc. - for more information please refer to:
https://en.wikipedia.org/wiki/FireWire