diff options
Diffstat (limited to 'Documentation/core-api')
| -rw-r--r-- | Documentation/core-api/cpu_hotplug.rst | 2 | ||||
| -rw-r--r-- | Documentation/core-api/gfp_mask-from-fs-io.rst | 20 | ||||
| -rw-r--r-- | Documentation/core-api/index.rst | 1 | ||||
| -rw-r--r-- | Documentation/core-api/min_heap.rst | 300 | ||||
| -rw-r--r-- | Documentation/core-api/packing.rst | 71 | ||||
| -rw-r--r-- | Documentation/core-api/printk-formats.rst | 20 | ||||
| -rw-r--r-- | Documentation/core-api/swiotlb.rst | 4 | ||||
| -rw-r--r-- | Documentation/core-api/workqueue.rst | 9 |
8 files changed, 412 insertions, 15 deletions
diff --git a/Documentation/core-api/cpu_hotplug.rst b/Documentation/core-api/cpu_hotplug.rst index a21dbf261be7..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 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 6a875743dd4b..563b8fc0002f 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -52,6 +52,7 @@ Library functionality that is used throughout the kernel. wrappers/atomic_bitops floating-point union_find + min_heap Low level entry and exit ======================== diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/min_heap.rst new file mode 100644 index 000000000000..0c636c8b7aa5 --- /dev/null +++ b/Documentation/core-api/min_heap.rst @@ -0,0 +1,300 @@ +.. SPDX-License-Identifier: GPL-2.0 + +============ +Min Heap API +============ + +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 { + int nr; /* Number of elements in the heap */ + int 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..821691f23c54 100644 --- a/Documentation/core-api/packing.rst +++ b/Documentation/core-api/packing.rst @@ -151,6 +151,77 @@ 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 ------------ diff --git a/Documentation/core-api/printk-formats.rst b/Documentation/core-api/printk-formats.rst index 14e093da3ccd..ecccc0473da9 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 ---------------------------- diff --git a/Documentation/core-api/swiotlb.rst b/Documentation/core-api/swiotlb.rst index cf06bae44ff8..9e0fe027dd3b 100644 --- a/Documentation/core-api/swiotlb.rst +++ b/Documentation/core-api/swiotlb.rst @@ -295,9 +295,9 @@ 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_tlb_map_single() allocates bounce buffer space to meet alloc_align_mask +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 swiotbl_tlb_unmap_single() is called with the bounce buffer address, the +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. diff --git a/Documentation/core-api/workqueue.rst b/Documentation/core-api/workqueue.rst index 16f861c9791e..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. @@ -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. |