diff options
Diffstat (limited to 'Documentation/core-api')
27 files changed, 1459 insertions, 94 deletions
diff --git a/Documentation/core-api/cgroup.rst b/Documentation/core-api/cgroup.rst new file mode 100644 index 000000000000..734ea21e1e17 --- /dev/null +++ b/Documentation/core-api/cgroup.rst @@ -0,0 +1,9 @@ +================== +Cgroup Kernel APIs +================== + +Device Memory Cgroup API (dmemcg) +================================= +.. kernel-doc:: kernel/cgroup/dmem.c + :export: + diff --git a/Documentation/core-api/cleanup.rst b/Documentation/core-api/cleanup.rst new file mode 100644 index 000000000000..527eb2f8ec6e --- /dev/null +++ b/Documentation/core-api/cleanup.rst @@ -0,0 +1,8 @@ +.. SPDX-License-Identifier: GPL-2.0 + +=========================== +Scope-based Cleanup Helpers +=========================== + +.. kernel-doc:: include/linux/cleanup.h + :doc: scope-based cleanup helpers diff --git a/Documentation/core-api/cpu_hotplug.rst b/Documentation/core-api/cpu_hotplug.rst index dcb0e379e5e8..e1b0eeabbb5e 100644 --- a/Documentation/core-api/cpu_hotplug.rst +++ b/Documentation/core-api/cpu_hotplug.rst @@ -616,7 +616,7 @@ ONLINE section for notifications on online and offline operation:: .... cpuhp_remove_instance(state, &inst2->node); .... - remove_multi_state(state); + cpuhp_remove_multi_state(state); Testing of hotplug states @@ -737,8 +737,9 @@ can process the event further. When changes to the CPUs in the system occur, the sysfs file /sys/devices/system/cpu/crash_hotplug contains '1' if the kernel -updates the kdump capture kernel list of CPUs itself (via elfcorehdr), -or '0' if userspace must update the kdump capture kernel list of CPUs. +updates the kdump capture kernel list of CPUs itself (via elfcorehdr and +other relevant kexec segment), or '0' if userspace must update the kdump +capture kernel list of CPUs. The availability depends on the CONFIG_HOTPLUG_CPU kernel configuration option. @@ -750,8 +751,9 @@ file can be used in a udev rule as follows: SUBSYSTEM=="cpu", ATTRS{crash_hotplug}=="1", GOTO="kdump_reload_end" For a CPU hot un/plug event, if the architecture supports kernel updates -of the elfcorehdr (which contains the list of CPUs), then the rule skips -the unload-then-reload of the kdump capture kernel. +of the elfcorehdr (which contains the list of CPUs) and other relevant +kexec segments, then the rule skips the unload-then-reload of the kdump +capture kernel. Kernel Inline Documentations Reference ====================================== diff --git a/Documentation/core-api/dma-api-howto.rst b/Documentation/core-api/dma-api-howto.rst index e8a55f9d61db..0bf31b6c4383 100644 --- a/Documentation/core-api/dma-api-howto.rst +++ b/Documentation/core-api/dma-api-howto.rst @@ -203,13 +203,33 @@ setting the DMA mask fails. In this manner, if a user of your driver reports that performance is bad or that the device is not even detected, you can ask them for the kernel messages to find out exactly why. -The standard 64-bit addressing device would do something like this:: +The 24-bit addressing device would do something like this:: - if (dma_set_mask_and_coherent(dev, DMA_BIT_MASK(64))) { + if (dma_set_mask_and_coherent(dev, DMA_BIT_MASK(24))) { dev_warn(dev, "mydev: No suitable DMA available\n"); goto ignore_this_device; } +The standard 64-bit addressing device would do something like this:: + + dma_set_mask_and_coherent(dev, DMA_BIT_MASK(64)) + +dma_set_mask_and_coherent() never return fail when DMA_BIT_MASK(64). Typical +error code like:: + + /* Wrong code */ + if (dma_set_mask_and_coherent(dev, DMA_BIT_MASK(64))) + dma_set_mask_and_coherent(dev, DMA_BIT_MASK(32)) + +dma_set_mask_and_coherent() will never return failure when bigger than 32. +So typical code like:: + + /* Recommended code */ + if (support_64bit) + dma_set_mask_and_coherent(dev, DMA_BIT_MASK(64)); + else + dma_set_mask_and_coherent(dev, DMA_BIT_MASK(32)); + If the device only supports 32-bit addressing for descriptors in the coherent allocations, but supports full 64-bits for streaming mappings it would look like this:: diff --git a/Documentation/core-api/entry.rst b/Documentation/core-api/entry.rst index e12f22ab33c7..a15f9b1767a2 100644 --- a/Documentation/core-api/entry.rst +++ b/Documentation/core-api/entry.rst @@ -18,7 +18,7 @@ exceptions`_, `NMI and NMI-like exceptions`_. Non-instrumentable code - noinstr --------------------------------- -Most instrumentation facilities depend on RCU, so intrumentation is prohibited +Most instrumentation facilities depend on RCU, so instrumentation is prohibited for entry code before RCU starts watching and exit code after RCU stops watching. In addition, many architectures must save and restore register state, which means that (for example) a breakpoint in the breakpoint entry code would diff --git a/Documentation/core-api/floating-point.rst b/Documentation/core-api/floating-point.rst new file mode 100644 index 000000000000..a8d0d4b05052 --- /dev/null +++ b/Documentation/core-api/floating-point.rst @@ -0,0 +1,78 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +Floating-point API +================== + +Kernel code is normally prohibited from using floating-point (FP) registers or +instructions, including the C float and double data types. This rule reduces +system call overhead, because the kernel does not need to save and restore the +userspace floating-point register state. + +However, occasionally drivers or library functions may need to include FP code. +This is supported by isolating the functions containing FP code to a separate +translation unit (a separate source file), and saving/restoring the FP register +state around calls to those functions. This creates "critical sections" of +floating-point usage. + +The reason for this isolation is to prevent the compiler from generating code +touching the FP registers outside these critical sections. Compilers sometimes +use FP registers to optimize inlined ``memcpy`` or variable assignment, as +floating-point registers may be wider than general-purpose registers. + +Usability of floating-point code within the kernel is architecture-specific. +Additionally, because a single kernel may be configured to support platforms +both with and without a floating-point unit, FPU availability must be checked +both at build time and at run time. + +Several architectures implement the generic kernel floating-point API from +``linux/fpu.h``, as described below. Some other architectures implement their +own unique APIs, which are documented separately. + +Build-time API +-------------- + +Floating-point code may be built if the option ``ARCH_HAS_KERNEL_FPU_SUPPORT`` +is enabled. For C code, such code must be placed in a separate file, and that +file must have its compilation flags adjusted using the following pattern:: + + CFLAGS_foo.o += $(CC_FLAGS_FPU) + CFLAGS_REMOVE_foo.o += $(CC_FLAGS_NO_FPU) + +Architectures are expected to define one or both of these variables in their +top-level Makefile as needed. For example:: + + CC_FLAGS_FPU := -mhard-float + +or:: + + CC_FLAGS_NO_FPU := -msoft-float + +Normal kernel code is assumed to use the equivalent of ``CC_FLAGS_NO_FPU``. + +Runtime API +----------- + +The runtime API is provided in ``linux/fpu.h``. This header cannot be included +from files implementing FP code (those with their compilation flags adjusted as +above). Instead, it must be included when defining the FP critical sections. + +.. c:function:: bool kernel_fpu_available( void ) + + This function reports if floating-point code can be used on this CPU or + platform. The value returned by this function is not expected to change + at runtime, so it only needs to be called once, not before every + critical section. + +.. c:function:: void kernel_fpu_begin( void ) + void kernel_fpu_end( void ) + + These functions create a floating-point critical section. It is only + valid to call ``kernel_fpu_begin()`` after a previous call to + ``kernel_fpu_available()`` returned ``true``. These functions are only + guaranteed to be callable from (preemptible or non-preemptible) process + context. + + Preemption may be disabled inside critical sections, so their size + should be minimized. They are *not* required to be reentrant. If the + caller expects to nest critical sections, it must implement its own + reference counting. diff --git a/Documentation/core-api/folio_queue.rst b/Documentation/core-api/folio_queue.rst new file mode 100644 index 000000000000..1fe7a9bc4b8d --- /dev/null +++ b/Documentation/core-api/folio_queue.rst @@ -0,0 +1,212 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +=========== +Folio Queue +=========== + +:Author: David Howells <dhowells@redhat.com> + +.. Contents: + + * Overview + * Initialisation + * Adding and removing folios + * Querying information about a folio + * Querying information about a folio_queue + * Folio queue iteration + * Folio marks + * Lockless simultaneous production/consumption issues + + +Overview +======== + +The folio_queue struct forms a single segment in a segmented list of folios +that can be used to form an I/O buffer. As such, the list can be iterated over +using the ITER_FOLIOQ iov_iter type. + +The publicly accessible members of the structure are:: + + struct folio_queue { + struct folio_queue *next; + struct folio_queue *prev; + ... + }; + +A pair of pointers are provided, ``next`` and ``prev``, that point to the +segments on either side of the segment being accessed. Whilst this is a +doubly-linked list, it is intentionally not a circular list; the outward +sibling pointers in terminal segments should be NULL. + +Each segment in the list also stores: + + * an ordered sequence of folio pointers, + * the size of each folio and + * three 1-bit marks per folio, + +but hese should not be accessed directly as the underlying data structure may +change, but rather the access functions outlined below should be used. + +The facility can be made accessible by:: + + #include <linux/folio_queue.h> + +and to use the iterator:: + + #include <linux/uio.h> + + +Initialisation +============== + +A segment should be initialised by calling:: + + void folioq_init(struct folio_queue *folioq); + +with a pointer to the segment to be initialised. Note that this will not +necessarily initialise all the folio pointers, so care must be taken to check +the number of folios added. + + +Adding and removing folios +========================== + +Folios can be set in the next unused slot in a segment struct by calling one +of:: + + unsigned int folioq_append(struct folio_queue *folioq, + struct folio *folio); + + unsigned int folioq_append_mark(struct folio_queue *folioq, + struct folio *folio); + +Both functions update the stored folio count, store the folio and note its +size. The second function also sets the first mark for the folio added. Both +functions return the number of the slot used. [!] Note that no attempt is made +to check that the capacity wasn't overrun and the list will not be extended +automatically. + +A folio can be excised by calling:: + + void folioq_clear(struct folio_queue *folioq, unsigned int slot); + +This clears the slot in the array and also clears all the marks for that folio, +but doesn't change the folio count - so future accesses of that slot must check +if the slot is occupied. + + +Querying information about a folio +================================== + +Information about the folio in a particular slot may be queried by the +following function:: + + struct folio *folioq_folio(const struct folio_queue *folioq, + unsigned int slot); + +If a folio has not yet been set in that slot, this may yield an undefined +pointer. The size of the folio in a slot may be queried with either of:: + + unsigned int folioq_folio_order(const struct folio_queue *folioq, + unsigned int slot); + + size_t folioq_folio_size(const struct folio_queue *folioq, + unsigned int slot); + +The first function returns the size as an order and the second as a number of +bytes. + + +Querying information about a folio_queue +======================================== + +Information may be retrieved about a particular segment with the following +functions:: + + unsigned int folioq_nr_slots(const struct folio_queue *folioq); + + unsigned int folioq_count(struct folio_queue *folioq); + + bool folioq_full(struct folio_queue *folioq); + +The first function returns the maximum capacity of a segment. It must not be +assumed that this won't vary between segments. The second returns the number +of folios added to a segments and the third is a shorthand to indicate if the +segment has been filled to capacity. + +Not that the count and fullness are not affected by clearing folios from the +segment. These are more about indicating how many slots in the array have been +initialised, and it assumed that slots won't get reused, but rather the segment +will get discarded as the queue is consumed. + + +Folio marks +=========== + +Folios within a queue can also have marks assigned to them. These marks can be +used to note information such as if a folio needs folio_put() calling upon it. +There are three marks available to be set for each folio. + +The marks can be set by:: + + void folioq_mark(struct folio_queue *folioq, unsigned int slot); + void folioq_mark2(struct folio_queue *folioq, unsigned int slot); + void folioq_mark3(struct folio_queue *folioq, unsigned int slot); + +Cleared by:: + + void folioq_unmark(struct folio_queue *folioq, unsigned int slot); + void folioq_unmark2(struct folio_queue *folioq, unsigned int slot); + void folioq_unmark3(struct folio_queue *folioq, unsigned int slot); + +And the marks can be queried by:: + + bool folioq_is_marked(const struct folio_queue *folioq, unsigned int slot); + bool folioq_is_marked2(const struct folio_queue *folioq, unsigned int slot); + bool folioq_is_marked3(const struct folio_queue *folioq, unsigned int slot); + +The marks can be used for any purpose and are not interpreted by this API. + + +Folio queue iteration +===================== + +A list of segments may be iterated over using the I/O iterator facility using +an ``iov_iter`` iterator of ``ITER_FOLIOQ`` type. The iterator may be +initialised with:: + + void iov_iter_folio_queue(struct iov_iter *i, unsigned int direction, + const struct folio_queue *folioq, + unsigned int first_slot, unsigned int offset, + size_t count); + +This may be told to start at a particular segment, slot and offset within a +queue. The iov iterator functions will follow the next pointers when advancing +and prev pointers when reverting when needed. + + +Lockless simultaneous production/consumption issues +=================================================== + +If properly managed, the list can be extended by the producer at the head end +and shortened by the consumer at the tail end simultaneously without the need +to take locks. The ITER_FOLIOQ iterator inserts appropriate barriers to aid +with this. + +Care must be taken when simultaneously producing and consuming a list. If the +last segment is reached and the folios it refers to are entirely consumed by +the IOV iterators, an iov_iter struct will be left pointing to the last segment +with a slot number equal to the capacity of that segment. The iterator will +try to continue on from this if there's another segment available when it is +used again, but care must be taken lest the segment got removed and freed by +the consumer before the iterator was advanced. + +It is recommended that the queue always contain at least one segment, even if +that segment has never been filled or is entirely spent. This prevents the +head and tail pointers from collapsing. + + +API Function Reference +====================== + +.. kernel-doc:: include/linux/folio_queue.h diff --git a/Documentation/core-api/genericirq.rst b/Documentation/core-api/genericirq.rst index 4a460639ab1c..25f94dfd66fa 100644 --- a/Documentation/core-api/genericirq.rst +++ b/Documentation/core-api/genericirq.rst @@ -210,7 +210,7 @@ implemented (simplified excerpt):: } } - noop(struct irq_data *data)) + noop(struct irq_data *data) { } @@ -410,6 +410,8 @@ which are used in the generic IRQ layer. .. kernel-doc:: include/linux/interrupt.h :internal: +.. kernel-doc:: include/linux/irqdomain.h + Public Functions Provided ========================= diff --git a/Documentation/core-api/gfp_mask-from-fs-io.rst b/Documentation/core-api/gfp_mask-from-fs-io.rst index e7c32a8de126..858b2fbcb36c 100644 --- a/Documentation/core-api/gfp_mask-from-fs-io.rst +++ b/Documentation/core-api/gfp_mask-from-fs-io.rst @@ -55,14 +55,16 @@ scope. What about __vmalloc(GFP_NOFS) ============================== -vmalloc doesn't support GFP_NOFS semantic because there are hardcoded -GFP_KERNEL allocations deep inside the allocator which are quite non-trivial -to fix up. That means that calling ``vmalloc`` with GFP_NOFS/GFP_NOIO is -almost always a bug. The good news is that the NOFS/NOIO semantic can be -achieved by the scope API. +Since v5.17, and specifically after the commit 451769ebb7e79 ("mm/vmalloc: +alloc GFP_NO{FS,IO} for vmalloc"), GFP_NOFS/GFP_NOIO are now supported in +``[k]vmalloc`` by implicitly using scope API. + +In earlier kernels ``vmalloc`` didn't support GFP_NOFS semantic because there +were hardcoded GFP_KERNEL allocations deep inside the allocator. That means +that calling ``vmalloc`` with GFP_NOFS/GFP_NOIO was almost always a bug. In the ideal world, upper layers should already mark dangerous contexts -and so no special care is required and vmalloc should be called without -any problems. Sometimes if the context is not really clear or there are -layering violations then the recommended way around that is to wrap ``vmalloc`` -by the scope API with a comment explaining the problem. +and so no special care is required and ``vmalloc`` should be called without any +problems. Sometimes if the context is not really clear or there are layering +violations then the recommended way around that (on pre-v5.17 kernels) is to +wrap ``vmalloc`` by the scope API with a comment explaining the problem. diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst index 7a3a08d81f11..e9789bd381d8 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -35,7 +35,9 @@ Library functionality that is used throughout the kernel. kobject kref + cleanup assoc_array + folio_queue xarray maple_tree idr @@ -48,6 +50,10 @@ Library functionality that is used throughout the kernel. errseq wrappers/atomic_t wrappers/atomic_bitops + floating-point + union_find + min_heap + parser Low level entry and exit ======================== @@ -102,7 +108,9 @@ more memory-management documentation in Documentation/mm/index.rst. dma-api-howto dma-attributes dma-isa-lpc + swiotlb mm-api + cgroup genalloc pin_user_pages boot-time-mm diff --git a/Documentation/core-api/kref.rst b/Documentation/core-api/kref.rst index c61eea6f1bf2..8db9ff03d952 100644 --- a/Documentation/core-api/kref.rst +++ b/Documentation/core-api/kref.rst @@ -3,7 +3,7 @@ Adding reference counters (krefs) to kernel objects =================================================== :Author: Corey Minyard <minyard@acm.org> -:Author: Thomas Hellstrom <thellstrom@vmware.com> +:Author: Thomas Hellström <thomas.hellstrom@linux.intel.com> A lot of this was lifted from Greg Kroah-Hartman's 2004 OLS paper and presentation on krefs, which can be found at: @@ -321,3 +321,8 @@ rcu grace period after release_entry_rcu was called. That can be accomplished by using kfree_rcu(entry, rhead) as done above, or by calling synchronize_rcu() before using kfree, but note that synchronize_rcu() may sleep for a substantial amount of time. + +Functions and structures +======================== + +.. kernel-doc:: include/linux/kref.h diff --git a/Documentation/core-api/memory-allocation.rst b/Documentation/core-api/memory-allocation.rst index 1c58d883b273..0f19dd524323 100644 --- a/Documentation/core-api/memory-allocation.rst +++ b/Documentation/core-api/memory-allocation.rst @@ -45,8 +45,9 @@ here we briefly outline their recommended usage: * If the allocation is performed from an atomic context, e.g interrupt handler, use ``GFP_NOWAIT``. This flag prevents direct reclaim and IO or filesystem operations. Consequently, under memory pressure - ``GFP_NOWAIT`` allocation is likely to fail. Allocations which - have a reasonable fallback should be using ``GFP_NOWARN``. + ``GFP_NOWAIT`` allocation is likely to fail. Users of this flag need + to provide a suitable fallback to cope with such failures where + appropriate. * If you think that accessing memory reserves is justified and the kernel will be stressed unless allocation succeeds, you may use ``GFP_ATOMIC``. * Untrusted allocations triggered from userspace should be a subject @@ -144,8 +145,10 @@ configuration, but it is a good practice to use `kmalloc` for objects smaller than page size. The address of a chunk allocated with `kmalloc` is aligned to at least -ARCH_KMALLOC_MINALIGN bytes. For sizes which are a power of two, the -alignment is also guaranteed to be at least the respective size. +ARCH_KMALLOC_MINALIGN bytes. For sizes which are a power of two, the +alignment is also guaranteed to be at least the respective size. For other +sizes, the alignment is guaranteed to be at least the largest power-of-two +divisor of the size. Chunks allocated with kmalloc() can be resized with krealloc(). Similarly to kmalloc_array(): a helper for resizing arrays is provided in the form of diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/min_heap.rst new file mode 100644 index 000000000000..9f57766581df --- /dev/null +++ b/Documentation/core-api/min_heap.rst @@ -0,0 +1,302 @@ +.. SPDX-License-Identifier: GPL-2.0 + +============ +Min Heap API +============ + +:Author: Kuan-Wei Chiu <visitorckw@gmail.com> + +Introduction +============ + +The Min Heap API provides a set of functions and macros for managing min-heaps +in the Linux kernel. A min-heap is a binary tree structure where the value of +each node is less than or equal to the values of its children, ensuring that +the smallest element is always at the root. + +This document provides a guide to the Min Heap API, detailing how to define and +use min-heaps. Users should not directly call functions with **__min_heap_*()** +prefixes, but should instead use the provided macro wrappers. + +In addition to the standard version of the functions, the API also includes a +set of inline versions for performance-critical scenarios. These inline +functions have the same names as their non-inline counterparts but include an +**_inline** suffix. For example, **__min_heap_init_inline** and its +corresponding macro wrapper **min_heap_init_inline**. The inline versions allow +custom comparison and swap functions to be called directly, rather than through +indirect function calls. This can significantly reduce overhead, especially +when CONFIG_MITIGATION_RETPOLINE is enabled, as indirect function calls become +more expensive. As with the non-inline versions, it is important to use the +macro wrappers for inline functions instead of directly calling the functions +themselves. + +Data Structures +=============== + +Min-Heap Definition +------------------- + +The core data structure for representing a min-heap is defined using the +**MIN_HEAP_PREALLOCATED** and **DEFINE_MIN_HEAP** macros. These macros allow +you to define a min-heap with a preallocated buffer or dynamically allocated +memory. + +Example: + +.. code-block:: c + + #define MIN_HEAP_PREALLOCATED(_type, _name, _nr) + struct _name { + size_t nr; /* Number of elements in the heap */ + size_t size; /* Maximum number of elements that can be held */ + _type *data; /* Pointer to the heap data */ + _type preallocated[_nr]; /* Static preallocated array */ + } + + #define DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0) + +A typical heap structure will include a counter for the number of elements +(`nr`), the maximum capacity of the heap (`size`), and a pointer to an array of +elements (`data`). Optionally, you can specify a static array for preallocated +heap storage using **MIN_HEAP_PREALLOCATED**. + +Min Heap Callbacks +------------------ + +The **struct min_heap_callbacks** provides customization options for ordering +elements in the heap and swapping them. It contains two function pointers: + +.. code-block:: c + + struct min_heap_callbacks { + bool (*less)(const void *lhs, const void *rhs, void *args); + void (*swp)(void *lhs, void *rhs, void *args); + }; + +- **less** is the comparison function used to establish the order of elements. +- **swp** is a function for swapping elements in the heap. If swp is set to + NULL, the default swap function will be used, which swaps the elements based on their size + +Macro Wrappers +============== + +The following macro wrappers are provided for interacting with the heap in a +user-friendly manner. Each macro corresponds to a function that operates on the +heap, and they abstract away direct calls to internal functions. + +Each macro accepts various parameters that are detailed below. + +Heap Initialization +-------------------- + +.. code-block:: c + + min_heap_init(heap, data, size); + +- **heap**: A pointer to the min-heap structure to be initialized. +- **data**: A pointer to the buffer where the heap elements will be stored. If + `NULL`, the preallocated buffer within the heap structure will be used. +- **size**: The maximum number of elements the heap can hold. + +This macro initializes the heap, setting its initial state. If `data` is +`NULL`, the preallocated memory inside the heap structure will be used for +storage. Otherwise, the user-provided buffer is used. The operation is **O(1)**. + +**Inline Version:** min_heap_init_inline(heap, data, size) + +Accessing the Top Element +------------------------- + +.. code-block:: c + + element = min_heap_peek(heap); + +- **heap**: A pointer to the min-heap from which to retrieve the smallest + element. + +This macro returns a pointer to the smallest element (the root) of the heap, or +`NULL` if the heap is empty. The operation is **O(1)**. + +**Inline Version:** min_heap_peek_inline(heap) + +Heap Insertion +-------------- + +.. code-block:: c + + success = min_heap_push(heap, element, callbacks, args); + +- **heap**: A pointer to the min-heap into which the element should be inserted. +- **element**: A pointer to the element to be inserted into the heap. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the + `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro inserts an element into the heap. It returns `true` if the insertion +was successful and `false` if the heap is full. The operation is **O(log n)**. + +**Inline Version:** min_heap_push_inline(heap, element, callbacks, args) + +Heap Removal +------------ + +.. code-block:: c + + success = min_heap_pop(heap, callbacks, args); + +- **heap**: A pointer to the min-heap from which to remove the smallest element. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the + `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro removes the smallest element (the root) from the heap. It returns +`true` if the element was successfully removed, or `false` if the heap is +empty. The operation is **O(log n)**. + +**Inline Version:** min_heap_pop_inline(heap, callbacks, args) + +Heap Maintenance +---------------- + +You can use the following macros to maintain the heap's structure: + +.. code-block:: c + + min_heap_sift_down(heap, pos, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **pos**: The index from which to start sifting down. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the + `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro restores the heap property by moving the element at the specified +index (`pos`) down the heap until it is in the correct position. The operation +is **O(log n)**. + +**Inline Version:** min_heap_sift_down_inline(heap, pos, callbacks, args) + +.. code-block:: c + + min_heap_sift_up(heap, idx, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **idx**: The index of the element to sift up. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the + `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro restores the heap property by moving the element at the specified +index (`idx`) up the heap. The operation is **O(log n)**. + +**Inline Version:** min_heap_sift_up_inline(heap, idx, callbacks, args) + +.. code-block:: c + + min_heapify_all(heap, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the + `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro ensures that the entire heap satisfies the heap property. It is +called when the heap is built from scratch or after many modifications. The +operation is **O(n)**. + +**Inline Version:** min_heapify_all_inline(heap, callbacks, args) + +Removing Specific Elements +-------------------------- + +.. code-block:: c + + success = min_heap_del(heap, idx, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **idx**: The index of the element to delete. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the + `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro removes an element at the specified index (`idx`) from the heap and +restores the heap property. The operation is **O(log n)**. + +**Inline Version:** min_heap_del_inline(heap, idx, callbacks, args) + +Other Utilities +=============== + +- **min_heap_full(heap)**: Checks whether the heap is full. + Complexity: **O(1)**. + +.. code-block:: c + + bool full = min_heap_full(heap); + +- `heap`: A pointer to the min-heap to check. + +This macro returns `true` if the heap is full, otherwise `false`. + +**Inline Version:** min_heap_full_inline(heap) + +- **min_heap_empty(heap)**: Checks whether the heap is empty. + Complexity: **O(1)**. + +.. code-block:: c + + bool empty = min_heap_empty(heap); + +- `heap`: A pointer to the min-heap to check. + +This macro returns `true` if the heap is empty, otherwise `false`. + +**Inline Version:** min_heap_empty_inline(heap) + +Example Usage +============= + +An example usage of the min-heap API would involve defining a heap structure, +initializing it, and inserting and removing elements as needed. + +.. code-block:: c + + #include <linux/min_heap.h> + + int my_less_function(const void *lhs, const void *rhs, void *args) { + return (*(int *)lhs < *(int *)rhs); + } + + struct min_heap_callbacks heap_cb = { + .less = my_less_function, /* Comparison function for heap order */ + .swp = NULL, /* Use default swap function */ + }; + + void example_usage(void) { + /* Pre-populate the buffer with elements */ + int buffer[5] = {5, 2, 8, 1, 3}; + /* Declare a min-heap */ + DEFINE_MIN_HEAP(int, my_heap); + + /* Initialize the heap with preallocated buffer and size */ + min_heap_init(&my_heap, buffer, 5); + + /* Build the heap using min_heapify_all */ + my_heap.nr = 5; /* Set the number of elements in the heap */ + min_heapify_all(&my_heap, &heap_cb, NULL); + + /* Peek at the top element (should be 1 in this case) */ + int *top = min_heap_peek(&my_heap); + pr_info("Top element: %d\n", *top); + + /* Pop the top element (1) and get the new top (2) */ + min_heap_pop(&my_heap, &heap_cb, NULL); + top = min_heap_peek(&my_heap); + pr_info("New top element: %d\n", *top); + + /* Insert a new element (0) and recheck the top */ + int new_element = 0; + min_heap_push(&my_heap, &new_element, &heap_cb, NULL); + top = min_heap_peek(&my_heap); + pr_info("Top element after insertion: %d\n", *top); + } diff --git a/Documentation/core-api/packing.rst b/Documentation/core-api/packing.rst index 3ed13bc9a195..0ce2078c8e13 100644 --- a/Documentation/core-api/packing.rst +++ b/Documentation/core-api/packing.rst @@ -151,16 +151,195 @@ the more significant 4-byte word. We always think of our offsets as if there were no quirk, and we translate them afterwards, before accessing the memory region. +Note on buffer lengths not multiple of 4 +---------------------------------------- + +To deal with memory layout quirks where groups of 4 bytes are laid out "little +endian" relative to each other, but "big endian" within the group itself, the +concept of groups of 4 bytes is intrinsic to the packing API (not to be +confused with the memory access, which is performed byte by byte, though). + +With buffer lengths not multiple of 4, this means one group will be incomplete. +Depending on the quirks, this may lead to discontinuities in the bit fields +accessible through the buffer. The packing API assumes discontinuities were not +the intention of the memory layout, so it avoids them by effectively logically +shortening the most significant group of 4 octets to the number of octets +actually available. + +Example with a 31 byte sized buffer given below. Physical buffer offsets are +implicit, and increase from left to right within a group, and from top to +bottom within a column. + +No quirks: + +:: + + 31 29 28 | Group 7 (most significant) + 27 26 25 24 | Group 6 + 23 22 21 20 | Group 5 + 19 18 17 16 | Group 4 + 15 14 13 12 | Group 3 + 11 10 9 8 | Group 2 + 7 6 5 4 | Group 1 + 3 2 1 0 | Group 0 (least significant) + +QUIRK_LSW32_IS_FIRST: + +:: + + 3 2 1 0 | Group 0 (least significant) + 7 6 5 4 | Group 1 + 11 10 9 8 | Group 2 + 15 14 13 12 | Group 3 + 19 18 17 16 | Group 4 + 23 22 21 20 | Group 5 + 27 26 25 24 | Group 6 + 30 29 28 | Group 7 (most significant) + +QUIRK_LITTLE_ENDIAN: + +:: + + 30 28 29 | Group 7 (most significant) + 24 25 26 27 | Group 6 + 20 21 22 23 | Group 5 + 16 17 18 19 | Group 4 + 12 13 14 15 | Group 3 + 8 9 10 11 | Group 2 + 4 5 6 7 | Group 1 + 0 1 2 3 | Group 0 (least significant) + +QUIRK_LITTLE_ENDIAN | QUIRK_LSW32_IS_FIRST: + +:: + + 0 1 2 3 | Group 0 (least significant) + 4 5 6 7 | Group 1 + 8 9 10 11 | Group 2 + 12 13 14 15 | Group 3 + 16 17 18 19 | Group 4 + 20 21 22 23 | Group 5 + 24 25 26 27 | Group 6 + 28 29 30 | Group 7 (most significant) + Intended use ------------ Drivers that opt to use this API first need to identify which of the above 3 quirk combinations (for a total of 8) match what the hardware documentation -describes. Then they should wrap the packing() function, creating a new -xxx_packing() that calls it using the proper QUIRK_* one-hot bits set. +describes. + +There are 3 supported usage patterns, detailed below. + +packing() +^^^^^^^^^ + +This API function is deprecated. The packing() function returns an int-encoded error code, which protects the programmer against incorrect API use. The errors are not expected to occur -during runtime, therefore it is reasonable for xxx_packing() to return void -and simply swallow those errors. Optionally it can dump stack or print the -error description. +during runtime, therefore it is reasonable to wrap packing() into a custom +function which returns void and swallows those errors. Optionally it can +dump stack or print the error description. + +.. code-block:: c + + void my_packing(void *buf, u64 *val, int startbit, int endbit, + size_t len, enum packing_op op) + { + int err; + + /* Adjust quirks accordingly */ + err = packing(buf, val, startbit, endbit, len, op, QUIRK_LSW32_IS_FIRST); + if (likely(!err)) + return; + + if (err == -EINVAL) { + pr_err("Start bit (%d) expected to be larger than end (%d)\n", + startbit, endbit); + } else if (err == -ERANGE) { + if ((startbit - endbit + 1) > 64) + pr_err("Field %d-%d too large for 64 bits!\n", + startbit, endbit); + else + pr_err("Cannot store %llx inside bits %d-%d (would truncate)\n", + *val, startbit, endbit); + } + dump_stack(); + } + +pack() and unpack() +^^^^^^^^^^^^^^^^^^^ + +These are const-correct variants of packing(), and eliminate the last "enum +packing_op op" argument. + +Calling pack(...) is equivalent, and preferred, to calling packing(..., PACK). + +Calling unpack(...) is equivalent, and preferred, to calling packing(..., UNPACK). + +pack_fields() and unpack_fields() +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The library exposes optimized functions for the scenario where there are many +fields represented in a buffer, and it encourages consumer drivers to avoid +repetitive calls to pack() and unpack() for each field, but instead use +pack_fields() and unpack_fields(), which reduces the code footprint. + +These APIs use field definitions in arrays of ``struct packed_field_u8`` or +``struct packed_field_u16``, allowing consumer drivers to minimize the size +of these arrays according to their custom requirements. + +The pack_fields() and unpack_fields() API functions are actually macros which +automatically select the appropriate function at compile time, based on the +type of the fields array passed in. + +An additional benefit over pack() and unpack() is that sanity checks on the +field definitions are handled at compile time with ``BUILD_BUG_ON`` rather +than only when the offending code is executed. These functions return void and +wrapping them to handle unexpected errors is not necessary. + +It is recommended, but not required, that you wrap your packed buffer into a +structured type with a fixed size. This generally makes it easier for the +compiler to enforce that the correct size buffer is used. + +Here is an example of how to use the fields APIs: + +.. code-block:: c + + /* Ordering inside the unpacked structure is flexible and can be different + * from the packed buffer. Here, it is optimized to reduce padding. + */ + struct data { + u64 field3; + u32 field4; + u16 field1; + u8 field2; + }; + + #define SIZE 13 + + typdef struct __packed { u8 buf[SIZE]; } packed_buf_t; + + static const struct packed_field_u8 fields[] = { + PACKED_FIELD(100, 90, struct data, field1), + PACKED_FIELD(90, 87, struct data, field2), + PACKED_FIELD(86, 30, struct data, field3), + PACKED_FIELD(29, 0, struct data, field4), + }; + + void unpack_your_data(const packed_buf_t *buf, struct data *unpacked) + { + BUILD_BUG_ON(sizeof(*buf) != SIZE; + + unpack_fields(buf, sizeof(*buf), unpacked, fields, + QUIRK_LITTLE_ENDIAN); + } + + void pack_your_data(const struct data *unpacked, packed_buf_t *buf) + { + BUILD_BUG_ON(sizeof(*buf) != SIZE; + + pack_fields(buf, sizeof(*buf), unpacked, fields, + QUIRK_LITTLE_ENDIAN); + } diff --git a/Documentation/core-api/parser.rst b/Documentation/core-api/parser.rst new file mode 100644 index 000000000000..45750d04b895 --- /dev/null +++ b/Documentation/core-api/parser.rst @@ -0,0 +1,17 @@ +.. SPDX-License-Identifier: GPL-2.0+ + +============== +Generic parser +============== + +Overview +======== + +The generic parser is a simple parser for parsing mount options, +filesystem options, driver options, subsystem options, etc. + +Parser API +========== + +.. kernel-doc:: lib/parser.c + :export: diff --git a/Documentation/core-api/pin_user_pages.rst b/Documentation/core-api/pin_user_pages.rst index 6b5f7e6e7155..c16ca163b55e 100644 --- a/Documentation/core-api/pin_user_pages.rst +++ b/Documentation/core-api/pin_user_pages.rst @@ -132,7 +132,7 @@ CASE 1: Direct IO (DIO) ----------------------- There are GUP references to pages that are serving as DIO buffers. These buffers are needed for a relatively short time (so they -are not "long term"). No special synchronization with page_mkclean() or +are not "long term"). No special synchronization with folio_mkclean() or munmap() is provided. Therefore, flags to set at the call site are: :: FOLL_PIN @@ -144,7 +144,7 @@ CASE 2: RDMA ------------ There are GUP references to pages that are serving as DMA buffers. These buffers are needed for a long time ("long term"). No special -synchronization with page_mkclean() or munmap() is provided. Therefore, flags +synchronization with folio_mkclean() or munmap() is provided. Therefore, flags to set at the call site are: :: FOLL_PIN | FOLL_LONGTERM @@ -170,7 +170,7 @@ callback, simply remove the range from the device's page tables. Either way, as long as the driver unpins the pages upon mmu notifier callback, then there is proper synchronization with both filesystem and mm -(page_mkclean(), munmap(), etc). Therefore, neither flag needs to be set. +(folio_mkclean(), munmap(), etc). Therefore, neither flag needs to be set. CASE 4: Pinning for struct page manipulation only ------------------------------------------------- @@ -196,20 +196,20 @@ INCORRECT (uses FOLL_GET calls): write to the data within the pages put_page() -page_maybe_dma_pinned(): the whole point of pinning -=================================================== +folio_maybe_dma_pinned(): the whole point of pinning +==================================================== -The whole point of marking pages as "DMA-pinned" or "gup-pinned" is to be able -to query, "is this page DMA-pinned?" That allows code such as page_mkclean() +The whole point of marking folios as "DMA-pinned" or "gup-pinned" is to be able +to query, "is this folio DMA-pinned?" That allows code such as folio_mkclean() (and file system writeback code in general) to make informed decisions about -what to do when a page cannot be unmapped due to such pins. +what to do when a folio cannot be unmapped due to such pins. What to do in those cases is the subject of a years-long series of discussions and debates (see the References at the end of this document). It's a TODO item here: fill in the details once that's worked out. Meanwhile, it's safe to say that having this available: :: - static inline bool page_maybe_dma_pinned(struct page *page) + static inline bool folio_maybe_dma_pinned(struct folio *folio) ...is a prerequisite to solving the long-running gup+DMA problem. diff --git a/Documentation/core-api/printk-formats.rst b/Documentation/core-api/printk-formats.rst index 4451ef501936..4bdc394e86af 100644 --- a/Documentation/core-api/printk-formats.rst +++ b/Documentation/core-api/printk-formats.rst @@ -209,12 +209,17 @@ Struct Resources :: %pr [mem 0x60000000-0x6fffffff flags 0x2200] or + [mem 0x60000000 flags 0x2200] or [mem 0x0000000060000000-0x000000006fffffff flags 0x2200] + [mem 0x0000000060000000 flags 0x2200] %pR [mem 0x60000000-0x6fffffff pref] or + [mem 0x60000000 pref] or [mem 0x0000000060000000-0x000000006fffffff pref] + [mem 0x0000000060000000 pref] For printing struct resources. The ``R`` and ``r`` specifiers result in a -printed resource with (R) or without (r) a decoded flags member. +printed resource with (R) or without (r) a decoded flags member. If start is +equal to end only print the start value. Passed by reference. @@ -231,6 +236,19 @@ width of the CPU data path. Passed by reference. +Struct Range +------------ + +:: + + %pra [range 0x0000000060000000-0x000000006fffffff] or + [range 0x0000000060000000] + +For printing struct range. struct range holds an arbitrary range of u64 +values. If start is equal to end only print the start value. + +Passed by reference. + DMA address types dma_addr_t ---------------------------- @@ -576,13 +594,12 @@ The field width is passed by value, the bitmap is passed by reference. Helper macros cpumask_pr_args() and nodemask_pr_args() are available to ease printing cpumask and nodemask. -Flags bitfields such as page flags, page_type, gfp_flags +Flags bitfields such as page flags and gfp_flags -------------------------------------------------------- :: %pGp 0x17ffffc0002036(referenced|uptodate|lru|active|private|node=0|zone=2|lastcpupid=0x1fffff) - %pGt 0xffffff7f(buddy) %pGg GFP_USER|GFP_DMA32|GFP_NOWARN %pGv read|exec|mayread|maywrite|mayexec|denywrite @@ -591,7 +608,6 @@ would construct the value. The type of flags is given by the third character. Currently supported are: - p - [p]age flags, expects value of type (``unsigned long *``) - - t - page [t]ype, expects value of type (``unsigned int *``) - v - [v]ma_flags, expects value of type (``unsigned long *``) - g - [g]fp_flags, expects value of type (``gfp_t *``) @@ -645,7 +661,7 @@ Do *not* use it from C. Thanks ====== -If you add other %p extensions, please extend <lib/test_printf.c> with -one or more test cases, if at all feasible. +If you add other %p extensions, please extend <lib/tests/printf_kunit.c> +with one or more test cases, if at all feasible. Thank you for your cooperation and attention. diff --git a/Documentation/core-api/printk-index.rst b/Documentation/core-api/printk-index.rst index 3062f37d119b..1979c5dd32fe 100644 --- a/Documentation/core-api/printk-index.rst +++ b/Documentation/core-api/printk-index.rst @@ -4,7 +4,7 @@ Printk Index ============ -There are many ways how to monitor the state of the system. One important +There are many ways to monitor the state of the system. One important source of information is the system log. It provides a lot of information, including more or less important warnings and error messages. @@ -101,7 +101,7 @@ their own wrappers adding __printk_index_emit(). Only few subsystem specific wrappers have been updated so far, for example, dev_printk(). As a result, the printk formats from -some subsystes can be missing in the printk index. +some subsystems can be missing in the printk index. Subsystem specific prefix diff --git a/Documentation/core-api/protection-keys.rst b/Documentation/core-api/protection-keys.rst index bf28ac0401f3..7eb7c6023e09 100644 --- a/Documentation/core-api/protection-keys.rst +++ b/Documentation/core-api/protection-keys.rst @@ -12,7 +12,10 @@ Pkeys Userspace (PKU) is a feature which can be found on: * Intel server CPUs, Skylake and later * Intel client CPUs, Tiger Lake (11th Gen Core) and later * Future AMD CPUs + * arm64 CPUs implementing the Permission Overlay Extension (FEAT_S1POE) +x86_64 +====== Pkeys work by dedicating 4 previously Reserved bits in each page table entry to a "protection key", giving 16 possible keys. @@ -28,6 +31,22 @@ register. The feature is only available in 64-bit mode, even though there is theoretically space in the PAE PTEs. These permissions are enforced on data access only and have no effect on instruction fetches. +arm64 +===== + +Pkeys use 3 bits in each page table entry, to encode a "protection key index", +giving 8 possible keys. + +Protections for each key are defined with a per-CPU user-writable system +register (POR_EL0). This is a 64-bit register encoding read, write and execute +overlay permissions for each protection key index. + +Being a CPU register, POR_EL0 is inherently thread-local, potentially giving +each thread a different set of protections from every other thread. + +Unlike x86_64, the protection key permissions also apply to instruction +fetches. + Syscalls ======== @@ -38,11 +57,10 @@ There are 3 system calls which directly interact with pkeys:: int pkey_mprotect(unsigned long start, size_t len, unsigned long prot, int pkey); -Before a pkey can be used, it must first be allocated with -pkey_alloc(). An application calls the WRPKRU instruction -directly in order to change access permissions to memory covered -with a key. In this example WRPKRU is wrapped by a C function -called pkey_set(). +Before a pkey can be used, it must first be allocated with pkey_alloc(). An +application writes to the architecture specific CPU register directly in order +to change access permissions to memory covered with a key. In this example +this is wrapped by a C function called pkey_set(). :: int real_prot = PROT_READ|PROT_WRITE; @@ -64,9 +82,9 @@ is no longer in use:: munmap(ptr, PAGE_SIZE); pkey_free(pkey); -.. note:: pkey_set() is a wrapper for the RDPKRU and WRPKRU instructions. - An example implementation can be found in - tools/testing/selftests/x86/protection_keys.c. +.. note:: pkey_set() is a wrapper around writing to the CPU register. + Example implementations can be found in + tools/testing/selftests/mm/pkey-{arm64,powerpc,x86}.h Behavior ======== @@ -96,3 +114,7 @@ with a read():: The kernel will send a SIGSEGV in both cases, but si_code will be set to SEGV_PKERR when violating protection keys versus SEGV_ACCERR when the plain mprotect() permissions are violated. + +Note that kernel accesses from a kthread (such as io_uring) will use a default +value for the protection key register and so will not be consistent with +userspace's value of the register or mprotect(). diff --git a/Documentation/core-api/refcount-vs-atomic.rst b/Documentation/core-api/refcount-vs-atomic.rst index 79a009ce11df..94e628c1eb49 100644 --- a/Documentation/core-api/refcount-vs-atomic.rst +++ b/Documentation/core-api/refcount-vs-atomic.rst @@ -86,7 +86,19 @@ Memory ordering guarantee changes: * none (both fully unordered) -case 2) - increment-based ops that return no value +case 2) - non-"Read/Modify/Write" (RMW) ops with release ordering +----------------------------------------------------------------- + +Function changes: + + * atomic_set_release() --> refcount_set_release() + +Memory ordering guarantee changes: + + * none (both provide RELEASE ordering) + + +case 3) - increment-based ops that return no value -------------------------------------------------- Function changes: @@ -98,7 +110,7 @@ Memory ordering guarantee changes: * none (both fully unordered) -case 3) - decrement-based RMW ops that return no value +case 4) - decrement-based RMW ops that return no value ------------------------------------------------------ Function changes: @@ -110,7 +122,7 @@ Memory ordering guarantee changes: * fully unordered --> RELEASE ordering -case 4) - increment-based RMW ops that return a value +case 5) - increment-based RMW ops that return a value ----------------------------------------------------- Function changes: @@ -126,7 +138,20 @@ Memory ordering guarantees changes: result of obtaining pointer to the object! -case 5) - generic dec/sub decrement-based RMW ops that return a value +case 6) - increment-based RMW ops with acquire ordering that return a value +--------------------------------------------------------------------------- + +Function changes: + + * atomic_inc_not_zero() --> refcount_inc_not_zero_acquire() + * no atomic counterpart --> refcount_add_not_zero_acquire() + +Memory ordering guarantees changes: + + * fully ordered --> ACQUIRE ordering on success + + +case 7) - generic dec/sub decrement-based RMW ops that return a value --------------------------------------------------------------------- Function changes: @@ -139,7 +164,7 @@ Memory ordering guarantees changes: * fully ordered --> RELEASE ordering + ACQUIRE ordering on success -case 6) other decrement-based RMW ops that return a value +case 8) other decrement-based RMW ops that return a value --------------------------------------------------------- Function changes: @@ -154,7 +179,7 @@ Memory ordering guarantees changes: .. note:: atomic_add_unless() only provides full order on success. -case 7) - lock-based RMW +case 9) - lock-based RMW ------------------------ Function changes: diff --git a/Documentation/core-api/swiotlb.rst b/Documentation/core-api/swiotlb.rst new file mode 100644 index 000000000000..9e0fe027dd3b --- /dev/null +++ b/Documentation/core-api/swiotlb.rst @@ -0,0 +1,321 @@ +.. SPDX-License-Identifier: GPL-2.0 + +=============== +DMA and swiotlb +=============== + +swiotlb is a memory buffer allocator used by the Linux kernel DMA layer. It is +typically used when a device doing DMA can't directly access the target memory +buffer because of hardware limitations or other requirements. In such a case, +the DMA layer calls swiotlb to allocate a temporary memory buffer that conforms +to the limitations. The DMA is done to/from this temporary memory buffer, and +the CPU copies the data between the temporary buffer and the original target +memory buffer. This approach is generically called "bounce buffering", and the +temporary memory buffer is called a "bounce buffer". + +Device drivers don't interact directly with swiotlb. Instead, drivers inform +the DMA layer of the DMA attributes of the devices they are managing, and use +the normal DMA map, unmap, and sync APIs when programming a device to do DMA. +These APIs use the device DMA attributes and kernel-wide settings to determine +if bounce buffering is necessary. If so, the DMA layer manages the allocation, +freeing, and sync'ing of bounce buffers. Since the DMA attributes are per +device, some devices in a system may use bounce buffering while others do not. + +Because the CPU copies data between the bounce buffer and the original target +memory buffer, doing bounce buffering is slower than doing DMA directly to the +original memory buffer, and it consumes more CPU resources. So it is used only +when necessary for providing DMA functionality. + +Usage Scenarios +--------------- +swiotlb was originally created to handle DMA for devices with addressing +limitations. As physical memory sizes grew beyond 4 GiB, some devices could +only provide 32-bit DMA addresses. By allocating bounce buffer memory below +the 4 GiB line, these devices with addressing limitations could still work and +do DMA. + +More recently, Confidential Computing (CoCo) VMs have the guest VM's memory +encrypted by default, and the memory is not accessible by the host hypervisor +and VMM. For the host to do I/O on behalf of the guest, the I/O must be +directed to guest memory that is unencrypted. CoCo VMs set a kernel-wide option +to force all DMA I/O to use bounce buffers, and the bounce buffer memory is set +up as unencrypted. The host does DMA I/O to/from the bounce buffer memory, and +the Linux kernel DMA layer does "sync" operations to cause the CPU to copy the +data to/from the original target memory buffer. The CPU copying bridges between +the unencrypted and the encrypted memory. This use of bounce buffers allows +device drivers to "just work" in a CoCo VM, with no modifications +needed to handle the memory encryption complexity. + +Other edge case scenarios arise for bounce buffers. For example, when IOMMU +mappings are set up for a DMA operation to/from a device that is considered +"untrusted", the device should be given access only to the memory containing +the data being transferred. But if that memory occupies only part of an IOMMU +granule, other parts of the granule may contain unrelated kernel data. Since +IOMMU access control is per-granule, the untrusted device can gain access to +the unrelated kernel data. This problem is solved by bounce buffering the DMA +operation and ensuring that unused portions of the bounce buffers do not +contain any unrelated kernel data. + +Core Functionality +------------------ +The primary swiotlb APIs are swiotlb_tbl_map_single() and +swiotlb_tbl_unmap_single(). The "map" API allocates a bounce buffer of a +specified size in bytes and returns the physical address of the buffer. The +buffer memory is physically contiguous. The expectation is that the DMA layer +maps the physical memory address to a DMA address, and returns the DMA address +to the driver for programming into the device. If a DMA operation specifies +multiple memory buffer segments, a separate bounce buffer must be allocated for +each segment. swiotlb_tbl_map_single() always does a "sync" operation (i.e., a +CPU copy) to initialize the bounce buffer to match the contents of the original +buffer. + +swiotlb_tbl_unmap_single() does the reverse. If the DMA operation might have +updated the bounce buffer memory and DMA_ATTR_SKIP_CPU_SYNC is not set, the +unmap does a "sync" operation to cause a CPU copy of the data from the bounce +buffer back to the original buffer. Then the bounce buffer memory is freed. + +swiotlb also provides "sync" APIs that correspond to the dma_sync_*() APIs that +a driver may use when control of a buffer transitions between the CPU and the +device. The swiotlb "sync" APIs cause a CPU copy of the data between the +original buffer and the bounce buffer. Like the dma_sync_*() APIs, the swiotlb +"sync" APIs support doing a partial sync, where only a subset of the bounce +buffer is copied to/from the original buffer. + +Core Functionality Constraints +------------------------------ +The swiotlb map/unmap/sync APIs must operate without blocking, as they are +called by the corresponding DMA APIs which may run in contexts that cannot +block. Hence the default memory pool for swiotlb allocations must be +pre-allocated at boot time (but see Dynamic swiotlb below). Because swiotlb +allocations must be physically contiguous, the entire default memory pool is +allocated as a single contiguous block. + +The need to pre-allocate the default swiotlb pool creates a boot-time tradeoff. +The pool should be large enough to ensure that bounce buffer requests can +always be satisfied, as the non-blocking requirement means requests can't wait +for space to become available. But a large pool potentially wastes memory, as +this pre-allocated memory is not available for other uses in the system. The +tradeoff is particularly acute in CoCo VMs that use bounce buffers for all DMA +I/O. These VMs use a heuristic to set the default pool size to ~6% of memory, +with a max of 1 GiB, which has the potential to be very wasteful of memory. +Conversely, the heuristic might produce a size that is insufficient, depending +on the I/O patterns of the workload in the VM. The dynamic swiotlb feature +described below can help, but has limitations. Better management of the swiotlb +default memory pool size remains an open issue. + +A single allocation from swiotlb is limited to IO_TLB_SIZE * IO_TLB_SEGSIZE +bytes, which is 256 KiB with current definitions. When a device's DMA settings +are such that the device might use swiotlb, the maximum size of a DMA segment +must be limited to that 256 KiB. This value is communicated to higher-level +kernel code via dma_map_mapping_size() and swiotlb_max_mapping_size(). If the +higher-level code fails to account for this limit, it may make requests that +are too large for swiotlb, and get a "swiotlb full" error. + +A key device DMA setting is "min_align_mask", which is a power of 2 minus 1 +so that some number of low order bits are set, or it may be zero. swiotlb +allocations ensure these min_align_mask bits of the physical address of the +bounce buffer match the same bits in the address of the original buffer. When +min_align_mask is non-zero, it may produce an "alignment offset" in the address +of the bounce buffer that slightly reduces the maximum size of an allocation. +This potential alignment offset is reflected in the value returned by +swiotlb_max_mapping_size(), which can show up in places like +/sys/block/<device>/queue/max_sectors_kb. For example, if a device does not use +swiotlb, max_sectors_kb might be 512 KiB or larger. If a device might use +swiotlb, max_sectors_kb will be 256 KiB. When min_align_mask is non-zero, +max_sectors_kb might be even smaller, such as 252 KiB. + +swiotlb_tbl_map_single() also takes an "alloc_align_mask" parameter. This +parameter specifies the allocation of bounce buffer space must start at a +physical address with the alloc_align_mask bits set to zero. But the actual +bounce buffer might start at a larger address if min_align_mask is non-zero. +Hence there may be pre-padding space that is allocated prior to the start of +the bounce buffer. Similarly, the end of the bounce buffer is rounded up to an +alloc_align_mask boundary, potentially resulting in post-padding space. Any +pre-padding or post-padding space is not initialized by swiotlb code. The +"alloc_align_mask" parameter is used by IOMMU code when mapping for untrusted +devices. It is set to the granule size - 1 so that the bounce buffer is +allocated entirely from granules that are not used for any other purpose. + +Data structures concepts +------------------------ +Memory used for swiotlb bounce buffers is allocated from overall system memory +as one or more "pools". The default pool is allocated during system boot with a +default size of 64 MiB. The default pool size may be modified with the +"swiotlb=" kernel boot line parameter. The default size may also be adjusted +due to other conditions, such as running in a CoCo VM, as described above. If +CONFIG_SWIOTLB_DYNAMIC is enabled, additional pools may be allocated later in +the life of the system. Each pool must be a contiguous range of physical +memory. The default pool is allocated below the 4 GiB physical address line so +it works for devices that can only address 32-bits of physical memory (unless +architecture-specific code provides the SWIOTLB_ANY flag). In a CoCo VM, the +pool memory must be decrypted before swiotlb is used. + +Each pool is divided into "slots" of size IO_TLB_SIZE, which is 2 KiB with +current definitions. IO_TLB_SEGSIZE contiguous slots (128 slots) constitute +what might be called a "slot set". When a bounce buffer is allocated, it +occupies one or more contiguous slots. A slot is never shared by multiple +bounce buffers. Furthermore, a bounce buffer must be allocated from a single +slot set, which leads to the maximum bounce buffer size being IO_TLB_SIZE * +IO_TLB_SEGSIZE. Multiple smaller bounce buffers may co-exist in a single slot +set if the alignment and size constraints can be met. + +Slots are also grouped into "areas", with the constraint that a slot set exists +entirely in a single area. Each area has its own spin lock that must be held to +manipulate the slots in that area. The division into areas avoids contending +for a single global spin lock when swiotlb is heavily used, such as in a CoCo +VM. The number of areas defaults to the number of CPUs in the system for +maximum parallelism, but since an area can't be smaller than IO_TLB_SEGSIZE +slots, it might be necessary to assign multiple CPUs to the same area. The +number of areas can also be set via the "swiotlb=" kernel boot parameter. + +When allocating a bounce buffer, if the area associated with the calling CPU +does not have enough free space, areas associated with other CPUs are tried +sequentially. For each area tried, the area's spin lock must be obtained before +trying an allocation, so contention may occur if swiotlb is relatively busy +overall. But an allocation request does not fail unless all areas do not have +enough free space. + +IO_TLB_SIZE, IO_TLB_SEGSIZE, and the number of areas must all be powers of 2 as +the code uses shifting and bit masking to do many of the calculations. The +number of areas is rounded up to a power of 2 if necessary to meet this +requirement. + +The default pool is allocated with PAGE_SIZE alignment. If an alloc_align_mask +argument to swiotlb_tbl_map_single() specifies a larger alignment, one or more +initial slots in each slot set might not meet the alloc_align_mask criterium. +Because a bounce buffer allocation can't cross a slot set boundary, eliminating +those initial slots effectively reduces the max size of a bounce buffer. +Currently, there's no problem because alloc_align_mask is set based on IOMMU +granule size, and granules cannot be larger than PAGE_SIZE. But if that were to +change in the future, the initial pool allocation might need to be done with +alignment larger than PAGE_SIZE. + +Dynamic swiotlb +--------------- +When CONFIG_SWIOTLB_DYNAMIC is enabled, swiotlb can do on-demand expansion of +the amount of memory available for allocation as bounce buffers. If a bounce +buffer request fails due to lack of available space, an asynchronous background +task is kicked off to allocate memory from general system memory and turn it +into an swiotlb pool. Creating an additional pool must be done asynchronously +because the memory allocation may block, and as noted above, swiotlb requests +are not allowed to block. Once the background task is kicked off, the bounce +buffer request creates a "transient pool" to avoid returning an "swiotlb full" +error. A transient pool has the size of the bounce buffer request, and is +deleted when the bounce buffer is freed. Memory for this transient pool comes +from the general system memory atomic pool so that creation does not block. +Creating a transient pool has relatively high cost, particularly in a CoCo VM +where the memory must be decrypted, so it is done only as a stopgap until the +background task can add another non-transient pool. + +Adding a dynamic pool has limitations. Like with the default pool, the memory +must be physically contiguous, so the size is limited to MAX_PAGE_ORDER pages +(e.g., 4 MiB on a typical x86 system). Due to memory fragmentation, a max size +allocation may not be available. The dynamic pool allocator tries smaller sizes +until it succeeds, but with a minimum size of 1 MiB. Given sufficient system +memory fragmentation, dynamically adding a pool might not succeed at all. + +The number of areas in a dynamic pool may be different from the number of areas +in the default pool. Because the new pool size is typically a few MiB at most, +the number of areas will likely be smaller. For example, with a new pool size +of 4 MiB and the 256 KiB minimum area size, only 16 areas can be created. If +the system has more than 16 CPUs, multiple CPUs must share an area, creating +more lock contention. + +New pools added via dynamic swiotlb are linked together in a linear list. +swiotlb code frequently must search for the pool containing a particular +swiotlb physical address, so that search is linear and not performant with a +large number of dynamic pools. The data structures could be improved for +faster searches. + +Overall, dynamic swiotlb works best for small configurations with relatively +few CPUs. It allows the default swiotlb pool to be smaller so that memory is +not wasted, with dynamic pools making more space available if needed (as long +as fragmentation isn't an obstacle). It is less useful for large CoCo VMs. + +Data Structure Details +---------------------- +swiotlb is managed with four primary data structures: io_tlb_mem, io_tlb_pool, +io_tlb_area, and io_tlb_slot. io_tlb_mem describes a swiotlb memory allocator, +which includes the default memory pool and any dynamic or transient pools +linked to it. Limited statistics on swiotlb usage are kept per memory allocator +and are stored in this data structure. These statistics are available under +/sys/kernel/debug/swiotlb when CONFIG_DEBUG_FS is set. + +io_tlb_pool describes a memory pool, either the default pool, a dynamic pool, +or a transient pool. The description includes the start and end addresses of +the memory in the pool, a pointer to an array of io_tlb_area structures, and a +pointer to an array of io_tlb_slot structures that are associated with the pool. + +io_tlb_area describes an area. The primary field is the spin lock used to +serialize access to slots in the area. The io_tlb_area array for a pool has an +entry for each area, and is accessed using a 0-based area index derived from the +calling processor ID. Areas exist solely to allow parallel access to swiotlb +from multiple CPUs. + +io_tlb_slot describes an individual memory slot in the pool, with size +IO_TLB_SIZE (2 KiB currently). The io_tlb_slot array is indexed by the slot +index computed from the bounce buffer address relative to the starting memory +address of the pool. The size of struct io_tlb_slot is 24 bytes, so the +overhead is about 1% of the slot size. + +The io_tlb_slot array is designed to meet several requirements. First, the DMA +APIs and the corresponding swiotlb APIs use the bounce buffer address as the +identifier for a bounce buffer. This address is returned by +swiotlb_tbl_map_single(), and then passed as an argument to +swiotlb_tbl_unmap_single() and the swiotlb_sync_*() functions. The original +memory buffer address obviously must be passed as an argument to +swiotlb_tbl_map_single(), but it is not passed to the other APIs. Consequently, +swiotlb data structures must save the original memory buffer address so that it +can be used when doing sync operations. This original address is saved in the +io_tlb_slot array. + +Second, the io_tlb_slot array must handle partial sync requests. In such cases, +the argument to swiotlb_sync_*() is not the address of the start of the bounce +buffer but an address somewhere in the middle of the bounce buffer, and the +address of the start of the bounce buffer isn't known to swiotlb code. But +swiotlb code must be able to calculate the corresponding original memory buffer +address to do the CPU copy dictated by the "sync". So an adjusted original +memory buffer address is populated into the struct io_tlb_slot for each slot +occupied by the bounce buffer. An adjusted "alloc_size" of the bounce buffer is +also recorded in each struct io_tlb_slot so a sanity check can be performed on +the size of the "sync" operation. The "alloc_size" field is not used except for +the sanity check. + +Third, the io_tlb_slot array is used to track available slots. The "list" field +in struct io_tlb_slot records how many contiguous available slots exist starting +at that slot. A "0" indicates that the slot is occupied. A value of "1" +indicates only the current slot is available. A value of "2" indicates the +current slot and the next slot are available, etc. The maximum value is +IO_TLB_SEGSIZE, which can appear in the first slot in a slot set, and indicates +that the entire slot set is available. These values are used when searching for +available slots to use for a new bounce buffer. They are updated when allocating +a new bounce buffer and when freeing a bounce buffer. At pool creation time, the +"list" field is initialized to IO_TLB_SEGSIZE down to 1 for the slots in every +slot set. + +Fourth, the io_tlb_slot array keeps track of any "padding slots" allocated to +meet alloc_align_mask requirements described above. When +swiotlb_tbl_map_single() allocates bounce buffer space to meet alloc_align_mask +requirements, it may allocate pre-padding space across zero or more slots. But +when swiotlb_tbl_unmap_single() is called with the bounce buffer address, the +alloc_align_mask value that governed the allocation, and therefore the +allocation of any padding slots, is not known. The "pad_slots" field records +the number of padding slots so that swiotlb_tbl_unmap_single() can free them. +The "pad_slots" value is recorded only in the first non-padding slot allocated +to the bounce buffer. + +Restricted pools +---------------- +The swiotlb machinery is also used for "restricted pools", which are pools of +memory separate from the default swiotlb pool, and that are dedicated for DMA +use by a particular device. Restricted pools provide a level of DMA memory +protection on systems with limited hardware protection capabilities, such as +those lacking an IOMMU. Such usage is specified by DeviceTree entries and +requires that CONFIG_DMA_RESTRICTED_POOL is set. Each restricted pool is based +on its own io_tlb_mem data structure that is independent of the main swiotlb +io_tlb_mem. + +Restricted pools add swiotlb_alloc() and swiotlb_free() APIs, which are called +from the dma_alloc_*() and dma_free_*() APIs. The swiotlb_alloc/free() APIs +allocate/free slots from/to the restricted pool directly and do not go through +swiotlb_tbl_map/unmap_single(). diff --git a/Documentation/core-api/symbol-namespaces.rst b/Documentation/core-api/symbol-namespaces.rst index 12e4aecdae94..06f766a6aab2 100644 --- a/Documentation/core-api/symbol-namespaces.rst +++ b/Documentation/core-api/symbol-namespaces.rst @@ -41,12 +41,12 @@ entries. In addition to the macros EXPORT_SYMBOL() and EXPORT_SYMBOL_GPL(), that allow exporting of kernel symbols to the kernel symbol table, variants of these are available to export symbols into a certain namespace: EXPORT_SYMBOL_NS() and -EXPORT_SYMBOL_NS_GPL(). They take one additional argument: the namespace. -Please note that due to macro expansion that argument needs to be a -preprocessor symbol. E.g. to export the symbol ``usb_stor_suspend`` into the +EXPORT_SYMBOL_NS_GPL(). They take one additional argument: the namespace as a +string constant. Note that this string must not contain whitespaces. +E.g. to export the symbol ``usb_stor_suspend`` into the namespace ``USB_STORAGE``, use:: - EXPORT_SYMBOL_NS(usb_stor_suspend, USB_STORAGE); + EXPORT_SYMBOL_NS(usb_stor_suspend, "USB_STORAGE"); The corresponding ksymtab entry struct ``kernel_symbol`` will have the member ``namespace`` set accordingly. A symbol that is exported without a namespace will @@ -68,7 +68,7 @@ is to define the default namespace in the ``Makefile`` of the subsystem. E.g. to export all symbols defined in usb-common into the namespace USB_COMMON, add a line like this to drivers/usb/common/Makefile:: - ccflags-y += -DDEFAULT_SYMBOL_NAMESPACE=USB_COMMON + ccflags-y += -DDEFAULT_SYMBOL_NAMESPACE='"USB_COMMON"' That will affect all EXPORT_SYMBOL() and EXPORT_SYMBOL_GPL() statements. A symbol exported with EXPORT_SYMBOL_NS() while this definition is present, will @@ -78,11 +78,10 @@ as this argument has preference over a default symbol namespace. A second option to define the default namespace is directly in the compilation unit as preprocessor statement. The above example would then read:: - #undef DEFAULT_SYMBOL_NAMESPACE - #define DEFAULT_SYMBOL_NAMESPACE USB_COMMON + #define DEFAULT_SYMBOL_NAMESPACE "USB_COMMON" -within the corresponding compilation unit before any EXPORT_SYMBOL macro is -used. +within the corresponding compilation unit before the #include for +<linux/export.h>. Typically it's placed before the first #include statement. 3. How to use Symbols exported in Namespaces ============================================ @@ -94,7 +93,7 @@ for the namespaces it uses symbols from. E.g. a module using the usb_stor_suspend symbol from above, needs to import the namespace USB_STORAGE using a statement like:: - MODULE_IMPORT_NS(USB_STORAGE); + MODULE_IMPORT_NS("USB_STORAGE"); This will create a ``modinfo`` tag in the module for each imported namespace. This has the side effect, that the imported namespaces of a module can be diff --git a/Documentation/core-api/this_cpu_ops.rst b/Documentation/core-api/this_cpu_ops.rst index 91acbcf30e9b..533ac5dd5750 100644 --- a/Documentation/core-api/this_cpu_ops.rst +++ b/Documentation/core-api/this_cpu_ops.rst @@ -138,12 +138,22 @@ get_cpu/put_cpu sequence requires. No processor number is available. Instead, the offset of the local per cpu area is simply added to the per cpu offset. -Note that this operation is usually used in a code segment when -preemption has been disabled. The pointer is then used to -access local per cpu data in a critical section. When preemption -is re-enabled this pointer is usually no longer useful since it may -no longer point to per cpu data of the current processor. - +Note that this operation can only be used in code segments where +smp_processor_id() may be used, for example, where preemption has been +disabled. The pointer is then used to access local per cpu data in a +critical section. When preemption is re-enabled this pointer is usually +no longer useful since it may no longer point to per cpu data of the +current processor. + +The special cases where it makes sense to obtain a per-CPU pointer in +preemptible code are addressed by raw_cpu_ptr(), but such use cases need +to handle cases where two different CPUs are accessing the same per cpu +variable, which might well be that of a third CPU. These use cases are +typically performance optimizations. For example, SRCU implements a pair +of counters as a pair of per-CPU variables, and rcu_read_lock_nmisafe() +uses raw_cpu_ptr() to get a pointer to some CPU's counter, and uses +atomic_inc_long() to handle migration between the raw_cpu_ptr() and +the atomic_inc_long(). Per cpu variables and offsets ----------------------------- diff --git a/Documentation/core-api/unaligned-memory-access.rst b/Documentation/core-api/unaligned-memory-access.rst index 1ee82419d8aa..5ceeb80eb539 100644 --- a/Documentation/core-api/unaligned-memory-access.rst +++ b/Documentation/core-api/unaligned-memory-access.rst @@ -203,7 +203,7 @@ Avoiding unaligned accesses =========================== The easiest way to avoid unaligned access is to use the get_unaligned() and -put_unaligned() macros provided by the <asm/unaligned.h> header file. +put_unaligned() macros provided by the <linux/unaligned.h> header file. Going back to an earlier example of code that potentially causes unaligned access:: diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api/union_find.rst new file mode 100644 index 000000000000..6df8b94fdb5a --- /dev/null +++ b/Documentation/core-api/union_find.rst @@ -0,0 +1,106 @@ +.. SPDX-License-Identifier: GPL-2.0 + +==================== +Union-Find in Linux +==================== + + +:Date: June 21, 2024 +:Author: Xavier <xavier_qy@163.com> + +What is union-find, and what is it used for? +------------------------------------------------ + +Union-find is a data structure used to handle the merging and querying +of disjoint sets. The primary operations supported by union-find are: + + Initialization: Resetting each element as an individual set, with + each set's initial parent node pointing to itself. + + Find: Determine which set a particular element belongs to, usually by + returning a “representative element” of that set. This operation + is used to check if two elements are in the same set. + + Union: Merge two sets into one. + +As a data structure used to maintain sets (groups), union-find is commonly +utilized to solve problems related to offline queries, dynamic connectivity, +and graph theory. It is also a key component in Kruskal's algorithm for +computing the minimum spanning tree, which is crucial in scenarios like +network routing. Consequently, union-find is widely referenced. Additionally, +union-find has applications in symbolic computation, register allocation, +and more. + +Space Complexity: O(n), where n is the number of nodes. + +Time Complexity: Using path compression can reduce the time complexity of +the find operation, and using union by rank can reduce the time complexity +of the union operation. These optimizations reduce the average time +complexity of each find and union operation to O(α(n)), where α(n) is the +inverse Ackermann function. This can be roughly considered a constant time +complexity for practical purposes. + +This document covers use of the Linux union-find implementation. For more +information on the nature and implementation of union-find, see: + + Wikipedia entry on union-find + https://en.wikipedia.org/wiki/Disjoint-set_data_structure + +Linux implementation of union-find +----------------------------------- + +Linux's union-find implementation resides in the file "lib/union_find.c". +To use it, "#include <linux/union_find.h>". + +The union-find data structure is defined as follows:: + + struct uf_node { + struct uf_node *parent; + unsigned int rank; + }; + +In this structure, parent points to the parent node of the current node. +The rank field represents the height of the current tree. During a union +operation, the tree with the smaller rank is attached under the tree with the +larger rank to maintain balance. + +Initializing union-find +----------------------- + +You can complete the initialization using either static or initialization +interface. Initialize the parent pointer to point to itself and set the rank +to 0. +Example:: + + struct uf_node my_node = UF_INIT_NODE(my_node); + +or + + uf_node_init(&my_node); + +Find the Root Node of union-find +-------------------------------- + +This operation is mainly used to determine whether two nodes belong to the same +set in the union-find. If they have the same root, they are in the same set. +During the find operation, path compression is performed to improve the +efficiency of subsequent find operations. +Example:: + + int connected; + struct uf_node *root1 = uf_find(&node_1); + struct uf_node *root2 = uf_find(&node_2); + if (root1 == root2) + connected = 1; + else + connected = 0; + +Union Two Sets in union-find +---------------------------- + +To union two sets in the union-find, you first find their respective root nodes +and then link the smaller node to the larger node based on the rank of the root +nodes. +Example:: + + uf_union(&node_1, &node_2); diff --git a/Documentation/core-api/workqueue.rst b/Documentation/core-api/workqueue.rst index ed73c612174d..e295835fc116 100644 --- a/Documentation/core-api/workqueue.rst +++ b/Documentation/core-api/workqueue.rst @@ -245,8 +245,8 @@ CPU which can be assigned to the work items of a wq. For example, with at the same time per CPU. This is always a per-CPU attribute, even for unbound workqueues. -The maximum limit for ``@max_active`` is 512 and the default value used -when 0 is specified is 256. These values are chosen sufficiently high +The maximum limit for ``@max_active`` is 2048 and the default value used +when 0 is specified is 1024. These values are chosen sufficiently high such that they are not the limiting factor while providing protection in runaway cases. @@ -260,7 +260,7 @@ Some users depend on strict execution ordering where only one work item is in flight at any given time and the work items are processed in queueing order. While the combination of ``@max_active`` of 1 and ``WQ_UNBOUND`` used to achieve this behavior, this is no longer the -case. Use ``alloc_ordered_queue()`` instead. +case. Use alloc_ordered_workqueue() instead. Example Execution Scenarios @@ -357,6 +357,11 @@ Guidelines difference in execution characteristics between using a dedicated wq and a system wq. + Note: If something may generate more than @max_active outstanding + work items (do stress test your producers), it may saturate a system + wq and potentially lead to deadlock. It should utilize its own + dedicated workqueue rather than the system wq. + * Unless work items are expected to consume a huge amount of CPU cycles, using a bound wq is usually beneficial due to the increased level of locality in wq operations and work item execution. @@ -671,7 +676,7 @@ configuration, worker pools and how workqueues map to the pools: :: events_unbound unbound 9 9 10 10 8 events_freezable percpu 0 2 4 6 events_power_efficient percpu 0 2 4 6 - events_freezable_power_ percpu 0 2 4 6 + events_freezable_pwr_ef percpu 0 2 4 6 rcu_gp percpu 0 2 4 6 rcu_par_gp percpu 0 2 4 6 slub_flushwq percpu 0 2 4 6 @@ -694,7 +699,7 @@ Use tools/workqueue/wq_monitor.py to monitor workqueue operations: :: events_unbound 38306 0 0.1 - 7 - - events_freezable 0 0 0.0 0 0 - - events_power_efficient 29598 0 0.2 0 0 - - - events_freezable_power_ 10 0 0.0 0 0 - - + events_freezable_pwr_ef 10 0 0.0 0 0 - - sock_diag_events 0 0 0.0 0 0 - - total infl CPUtime CPUhog CMW/RPR mayday rescued @@ -704,7 +709,7 @@ Use tools/workqueue/wq_monitor.py to monitor workqueue operations: :: events_unbound 38322 0 0.1 - 7 - - events_freezable 0 0 0.0 0 0 - - events_power_efficient 29603 0 0.2 0 0 - - - events_freezable_power_ 10 0 0.0 0 0 - - + events_freezable_pwr_ef 10 0 0.0 0 0 - - sock_diag_events 0 0 0.0 0 0 - - ... diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index 77e0ece2b1d6..c6c91cbd0c3c 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -42,8 +42,8 @@ call xa_tag_pointer() to create an entry with a tag, xa_untag_pointer() to turn a tagged entry back into an untagged pointer and xa_pointer_tag() to retrieve the tag of an entry. Tagged pointers use the same bits that are used to distinguish value entries from normal pointers, so you must -decide whether they want to store value entries or tagged pointers in -any particular XArray. +decide whether you want to store value entries or tagged pointers in any +particular XArray. The XArray does not support storing IS_ERR() pointers as some conflict with value entries or internal entries. @@ -52,8 +52,9 @@ An unusual feature of the XArray is the ability to create entries which occupy a range of indices. Once stored to, looking up any index in the range will return the same entry as looking up any other index in the range. Storing to any index will store to all of them. Multi-index -entries can be explicitly split into smaller entries, or storing ``NULL`` -into any entry will cause the XArray to forget about the range. +entries can be explicitly split into smaller entries. Unsetting (using +xa_erase() or xa_store() with ``NULL``) any entry will cause the XArray +to forget about the range. Normal API ========== @@ -63,13 +64,14 @@ for statically allocated XArrays or xa_init() for dynamically allocated ones. A freshly-initialised XArray contains a ``NULL`` pointer at every index. -You can then set entries using xa_store() and get entries -using xa_load(). xa_store will overwrite any entry with the -new entry and return the previous entry stored at that index. You can -use xa_erase() instead of calling xa_store() with a -``NULL`` entry. There is no difference between an entry that has never -been stored to, one that has been erased and one that has most recently -had ``NULL`` stored to it. +You can then set entries using xa_store() and get entries using +xa_load(). xa_store() will overwrite any entry with the new entry and +return the previous entry stored at that index. You can unset entries +using xa_erase() or by setting the entry to ``NULL`` using xa_store(). +There is no difference between an entry that has never been stored to +and one that has been erased with xa_erase(); an entry that has most +recently had ``NULL`` stored to it is also equivalent except if the +XArray was initialized with ``XA_FLAGS_ALLOC``. You can conditionally replace an entry at an index by using xa_cmpxchg(). Like cmpxchg(), it will only succeed if @@ -487,7 +489,19 @@ Storing ``NULL`` into any index of a multi-index entry will set the entry at every index to ``NULL`` and dissolve the tie. A multi-index entry can be split into entries occupying smaller ranges by calling xas_split_alloc() without the xa_lock held, followed by taking the lock -and calling xas_split(). +and calling xas_split() or calling xas_try_split() with xa_lock. The +difference between xas_split_alloc()+xas_split() and xas_try_alloc() is +that xas_split_alloc() + xas_split() split the entry from the original +order to the new order in one shot uniformly, whereas xas_try_split() +iteratively splits the entry containing the index non-uniformly. +For example, to split an order-9 entry, which takes 2^(9-6)=8 slots, +assuming ``XA_CHUNK_SHIFT`` is 6, xas_split_alloc() + xas_split() need +8 xa_node. xas_try_split() splits the order-9 entry into +2 order-8 entries, then split one order-8 entry, based on the given index, +to 2 order-7 entries, ..., and split one order-1 entry to 2 order-0 entries. +When splitting the order-6 entry and a new xa_node is needed, xas_try_split() +will try to allocate one if possible. As a result, xas_try_split() would only +need 1 xa_node instead of 8. Functions and structures ======================== |