summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2024-11-25 16:09:48 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2024-11-25 16:09:48 -0800
commitf5f4745a7f057b58c9728ee4e2c5d6d79f382fe7 (patch)
tree7e5ddce694baa3a0d6c8d7a5b2f59e8778315ee9
parent7f4f3b14e8079ecde096bd734af10e30d40c27b7 (diff)
parent2c259a91d8d23a8266092b0dd51b8092877717a4 (diff)
downloadlinux-f5f4745a7f057b58c9728ee4e2c5d6d79f382fe7.tar.gz
linux-f5f4745a7f057b58c9728ee4e2c5d6d79f382fe7.tar.bz2
linux-f5f4745a7f057b58c9728ee4e2c5d6d79f382fe7.zip
Merge tag 'mm-nonmm-stable-2024-11-24-02-05' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Pull non-MM updates from Andrew Morton: - The series "resource: A couple of cleanups" from Andy Shevchenko performs some cleanups in the resource management code - The series "Improve the copy of task comm" from Yafang Shao addresses possible race-induced overflows in the management of task_struct.comm[] - The series "Remove unnecessary header includes from {tools/}lib/list_sort.c" from Kuan-Wei Chiu adds some cleanups and a small fix to the list_sort library code and to its selftest - The series "Enhance min heap API with non-inline functions and optimizations" also from Kuan-Wei Chiu optimizes and cleans up the min_heap library code - The series "nilfs2: Finish folio conversion" from Ryusuke Konishi finishes off nilfs2's folioification - The series "add detect count for hung tasks" from Lance Yang adds more userspace visibility into the hung-task detector's activity - Apart from that, singelton patches in many places - please see the individual changelogs for details * tag 'mm-nonmm-stable-2024-11-24-02-05' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm: (71 commits) gdb: lx-symbols: do not error out on monolithic build kernel/reboot: replace sprintf() with sysfs_emit() lib: util_macros_kunit: add kunit test for util_macros.h util_macros.h: fix/rework find_closest() macros Improve consistency of '#error' directive messages ocfs2: fix uninitialized value in ocfs2_file_read_iter() hung_task: add docs for hung_task_detect_count hung_task: add detect count for hung tasks dma-buf: use atomic64_inc_return() in dma_buf_getfile() fs/proc/kcore.c: fix coccinelle reported ERROR instances resource: avoid unnecessary resource tree walking in __region_intersects() ocfs2: remove unused errmsg function and table ocfs2: cluster: fix a typo lib/scatterlist: use sg_phys() helper checkpatch: always parse orig_commit in fixes tag nilfs2: convert metadata aops from writepage to writepages nilfs2: convert nilfs_recovery_copy_block() to take a folio nilfs2: convert nilfs_page_count_clean_buffers() to take a folio nilfs2: remove nilfs_writepage nilfs2: convert checkpoint file to be folio-based ...
-rw-r--r--Documentation/admin-guide/sysctl/kernel.rst9
-rw-r--r--Documentation/core-api/index.rst1
-rw-r--r--Documentation/core-api/min_heap.rst300
-rw-r--r--MAINTAINERS9
-rw-r--r--arch/alpha/include/asm/spinlock_types.h2
-rw-r--r--arch/arm/include/asm/spinlock_types.h2
-rw-r--r--arch/arm64/include/asm/spinlock_types.h2
-rw-r--r--arch/hexagon/include/asm/spinlock_types.h2
-rw-r--r--arch/powerpc/include/asm/simple_spinlock_types.h2
-rw-r--r--arch/powerpc/include/asm/spinlock_types.h2
-rw-r--r--arch/s390/include/asm/spinlock_types.h2
-rw-r--r--arch/sh/include/asm/spinlock_types.h2
-rw-r--r--arch/xtensa/include/asm/spinlock_types.h2
-rw-r--r--drivers/gpu/drm/drm_framebuffer.c2
-rw-r--r--drivers/gpu/drm/i915/i915_gpu_error.c6
-rw-r--r--drivers/md/bcache/Kconfig1
-rw-r--r--drivers/md/bcache/alloc.c11
-rw-r--r--drivers/md/bcache/bset.c14
-rw-r--r--drivers/md/bcache/extents.c10
-rw-r--r--drivers/md/bcache/movinggc.c10
-rw-r--r--drivers/md/dm-vdo/Kconfig1
-rw-r--r--drivers/md/dm-vdo/repair.c2
-rw-r--r--drivers/md/dm-vdo/slab-depot.c10
-rw-r--r--fs/bcachefs/Kconfig1
-rw-r--r--fs/bcachefs/clock.c25
-rw-r--r--fs/bcachefs/ec.c19
-rw-r--r--fs/exec.c10
-rw-r--r--fs/nilfs2/alloc.c148
-rw-r--r--fs/nilfs2/alloc.h4
-rw-r--r--fs/nilfs2/cpfile.c383
-rw-r--r--fs/nilfs2/dat.c98
-rw-r--r--fs/nilfs2/dir.c2
-rw-r--r--fs/nilfs2/ifile.c10
-rw-r--r--fs/nilfs2/ifile.h4
-rw-r--r--fs/nilfs2/inode.c35
-rw-r--r--fs/nilfs2/mdt.c40
-rw-r--r--fs/nilfs2/page.c4
-rw-r--r--fs/nilfs2/page.h4
-rw-r--r--fs/nilfs2/recovery.c17
-rw-r--r--fs/nilfs2/segbuf.c17
-rw-r--r--fs/nilfs2/sufile.c160
-rw-r--r--fs/ocfs2/alloc.c2
-rw-r--r--fs/ocfs2/aops.h2
-rw-r--r--fs/ocfs2/cluster/quorum.c2
-rw-r--r--fs/ocfs2/dlm/dlmapi.h2
-rw-r--r--fs/ocfs2/dlm/dlmdebug.c53
-rw-r--r--fs/ocfs2/file.c4
-rw-r--r--fs/ocfs2/quota.h1
-rw-r--r--fs/proc/array.c2
-rw-r--r--fs/proc/kcore.c10
-rw-r--r--include/acpi/platform/aclinux.h2
-rw-r--r--include/linux/compiler-clang.h2
-rw-r--r--include/linux/compiler-gcc.h2
-rw-r--r--include/linux/min_heap.h357
-rw-r--r--include/linux/notifier.h2
-rw-r--r--include/linux/percpu-defs.h21
-rw-r--r--include/linux/pm_wakeup.h2
-rw-r--r--include/linux/rwlock.h2
-rw-r--r--include/linux/rwlock_api_smp.h2
-rw-r--r--include/linux/scatterlist.h2
-rw-r--r--include/linux/sched.h28
-rw-r--r--include/linux/spinlock_api_smp.h2
-rw-r--r--include/linux/spinlock_types_up.h2
-rw-r--r--include/linux/spinlock_up.h2
-rw-r--r--include/linux/util_macros.h56
-rw-r--r--init/Kconfig1
-rw-r--r--ipc/msg.c2
-rw-r--r--ipc/namespace.c4
-rw-r--r--kernel/auditsc.c6
-rw-r--r--kernel/crash_core.c6
-rw-r--r--kernel/events/core.c15
-rw-r--r--kernel/events/hw_breakpoint.c4
-rw-r--r--kernel/hung_task.c18
-rw-r--r--kernel/kthread.c2
-rw-r--r--kernel/notifier.c8
-rw-r--r--kernel/reboot.c15
-rw-r--r--kernel/resource.c66
-rw-r--r--kernel/watchdog.c3
-rw-r--r--lib/Kconfig6
-rw-r--r--lib/Kconfig.debug59
-rw-r--r--lib/Makefile6
-rw-r--r--lib/crc16_kunit.c155
-rw-r--r--lib/list-test.c4
-rw-r--r--lib/list_sort.c3
-rw-r--r--lib/min_heap.c70
-rw-r--r--lib/scatterlist.c4
-rw-r--r--lib/test_min_heap.c16
-rw-r--r--lib/util_macros_kunit.c240
-rw-r--r--mm/util.c62
-rw-r--r--samples/hw_breakpoint/data_breakpoint.c4
-rwxr-xr-xscripts/checkpatch.pl37
-rwxr-xr-xscripts/decode_stacktrace.sh7
-rw-r--r--scripts/gdb/linux/modules.py3
-rw-r--r--scripts/gdb/linux/symbols.py3
-rw-r--r--scripts/spelling.txt33
-rw-r--r--security/lsm_audit.c4
-rw-r--r--security/selinux/selinuxfs.c2
-rw-r--r--tools/bpf/bpftool/pids.c2
-rw-r--r--tools/include/linux/compiler-gcc.h2
-rw-r--r--tools/lib/list_sort.c2
-rw-r--r--tools/perf/check-header_ignore_hunks/lib/list_sort.c11
-rw-r--r--tools/testing/shared/linux.c14
102 files changed, 1951 insertions, 895 deletions
diff --git a/Documentation/admin-guide/sysctl/kernel.rst b/Documentation/admin-guide/sysctl/kernel.rst
index f8bc1630eba0..b2b36d0c3094 100644
--- a/Documentation/admin-guide/sysctl/kernel.rst
+++ b/Documentation/admin-guide/sysctl/kernel.rst
@@ -401,6 +401,15 @@ The upper bound on the number of tasks that are checked.
This file shows up if ``CONFIG_DETECT_HUNG_TASK`` is enabled.
+hung_task_detect_count
+======================
+
+Indicates the total number of tasks that have been detected as hung since
+the system boot.
+
+This file shows up if ``CONFIG_DETECT_HUNG_TASK`` is enabled.
+
+
hung_task_timeout_secs
======================
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