From cf28d7716e0c777f593948eea109dc273047dac7 Mon Sep 17 00:00:00 2001 From: Wei-Hsin Yeh Date: Sun, 12 May 2024 13:42:11 +0800 Subject: include/linux/jhash.h: fix typos Drop one '-' to adhere to coding style. Replace 'arbitray' with 'arbitrary'. Link: https://lkml.kernel.org/r/20240512054211.24726-1-weihsinyeh168@gmail.com Signed-off-by: Wei-Hsin Yeh Signed-off-by: Andrew Morton --- include/linux/jhash.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'include/linux') diff --git a/include/linux/jhash.h b/include/linux/jhash.h index ab7f8c152b89..fa26a2dd3b52 100644 --- a/include/linux/jhash.h +++ b/include/linux/jhash.h @@ -31,7 +31,7 @@ /* Mask the hash value, i.e (value & jhash_mask(n)) instead of (value % n) */ #define jhash_mask(n) (jhash_size(n)-1) -/* __jhash_mix -- mix 3 32-bit values reversibly. */ +/* __jhash_mix - mix 3 32-bit values reversibly. */ #define __jhash_mix(a, b, c) \ { \ a -= c; a ^= rol32(c, 4); c += b; \ @@ -60,7 +60,7 @@ /* jhash - hash an arbitrary key * @k: sequence of bytes as key * @length: the length of the key - * @initval: the previous hash, or an arbitray value + * @initval: the previous hash, or an arbitrary value * * The generic version, hashes an arbitrary sequence of bytes. * No alignment or length assumptions are made about the input key. @@ -110,7 +110,7 @@ static inline u32 jhash(const void *key, u32 length, u32 initval) /* jhash2 - hash an array of u32's * @k: the key which must be an array of u32's * @length: the number of u32's in the key - * @initval: the previous hash, or an arbitray value + * @initval: the previous hash, or an arbitrary value * * Returns the hash value of the key. */ -- cgit v1.2.3 From 873ce25766019dd017c1a3a10c19ac3fc4bf24aa Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:46 +0800 Subject: lib min_heap: add type safe interface Implement a type-safe interface for min_heap using strong type pointers instead of void * in the data field. This change includes adding small macro wrappers around functions, enabling the use of __minheap_cast and __minheap_obj_size macros for type casting and obtaining element size. This implementation removes the necessity of passing element size in min_heap_callbacks. Additionally, introduce the MIN_HEAP_PREALLOCATED macro for preallocating some elements. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu Link: https://lkml.kernel.org/r/20240524152958.919343-5-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 79 +++++++++++++++++++++++++++++++----------------- 1 file changed, 51 insertions(+), 28 deletions(-) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d52daf45861b..92830f41642a 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -7,45 +7,53 @@ #include /** - * struct min_heap - Data structure to hold a min-heap. - * @data: Start of array holding the heap elements. + * Data structure to hold a min-heap. * @nr: Number of elements currently in the heap. * @size: Maximum number of elements that can be held in current storage. + * @data: Pointer to the start of array holding the heap elements. + * @preallocated: Start of the static preallocated array holding the heap elements. */ -struct min_heap { - void *data; - int nr; - int size; -}; +#define MIN_HEAP_PREALLOCATED(_type, _name, _nr) \ +struct _name { \ + int nr; \ + int size; \ + _type *data; \ + _type preallocated[_nr]; \ +} + +#define DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0) + +typedef DEFINE_MIN_HEAP(char, min_heap_char) min_heap_char; + +#define __minheap_cast(_heap) (typeof((_heap)->data[0]) *) +#define __minheap_obj_size(_heap) sizeof((_heap)->data[0]) /** * struct min_heap_callbacks - Data/functions to customise the min_heap. - * @elem_size: The nr of each element in bytes. * @less: Partial order function for this heap. * @swp: Swap elements function. */ struct min_heap_callbacks { - int elem_size; bool (*less)(const void *lhs, const void *rhs); void (*swp)(void *lhs, void *rhs); }; /* Sift the element at pos down the heap. */ static __always_inline -void min_heapify(struct min_heap *heap, int pos, +void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func) { void *left, *right; void *data = heap->data; - void *root = data + pos * func->elem_size; + void *root = data + pos * elem_size; int i = pos, j; /* Find the sift-down path all the way to the leaves. */ for (;;) { if (i * 2 + 2 >= heap->nr) break; - left = data + (i * 2 + 1) * func->elem_size; - right = data + (i * 2 + 2) * func->elem_size; + left = data + (i * 2 + 1) * elem_size; + right = data + (i * 2 + 2) * elem_size; i = func->less(left, right) ? i * 2 + 1 : i * 2 + 2; } @@ -54,31 +62,37 @@ void min_heapify(struct min_heap *heap, int pos, i = i * 2 + 1; /* Backtrack to the correct location. */ - while (i != pos && func->less(root, data + i * func->elem_size)) + while (i != pos && func->less(root, data + i * elem_size)) i = (i - 1) / 2; /* Shift the element into its correct place. */ j = i; while (i != pos) { i = (i - 1) / 2; - func->swp(data + i * func->elem_size, data + j * func->elem_size); + func->swp(data + i * elem_size, data + j * elem_size); } } +#define min_heapify(_heap, _pos, _func) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline -void min_heapify_all(struct min_heap *heap, +void __min_heapify_all(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { int i; for (i = heap->nr / 2 - 1; i >= 0; i--) - min_heapify(heap, i, func); + __min_heapify(heap, i, elem_size, func); } +#define min_heapify_all(_heap, _func) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) + /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void min_heap_pop(struct min_heap *heap, +void __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { void *data = heap->data; @@ -88,27 +102,33 @@ void min_heap_pop(struct min_heap *heap, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; - memcpy(data, data + (heap->nr * func->elem_size), func->elem_size); - min_heapify(heap, 0, func); + memcpy(data, data + (heap->nr * elem_size), elem_size); + __min_heapify(heap, 0, elem_size, func); } +#define min_heap_pop(_heap, _func) \ + __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) + /* * Remove the minimum element and then push the given element. The * implementation performs 1 sift (O(log2(nr))) and is therefore more * efficient than a pop followed by a push that does 2. */ static __always_inline -void min_heap_pop_push(struct min_heap *heap, - const void *element, +void __min_heap_pop_push(min_heap_char *heap, + const void *element, size_t elem_size, const struct min_heap_callbacks *func) { - memcpy(heap->data, element, func->elem_size); - min_heapify(heap, 0, func); + memcpy(heap->data, element, elem_size); + __min_heapify(heap, 0, elem_size, func); } +#define min_heap_pop_push(_heap, _element, _func) \ + __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func) + /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void min_heap_push(struct min_heap *heap, const void *element, +void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, const struct min_heap_callbacks *func) { void *data = heap->data; @@ -120,17 +140,20 @@ void min_heap_push(struct min_heap *heap, const void *element, /* Place at the end of data. */ pos = heap->nr; - memcpy(data + (pos * func->elem_size), element, func->elem_size); + memcpy(data + (pos * elem_size), element, elem_size); heap->nr++; /* Sift child at pos up. */ for (; pos > 0; pos = (pos - 1) / 2) { - child = data + (pos * func->elem_size); - parent = data + ((pos - 1) / 2) * func->elem_size; + child = data + (pos * elem_size); + parent = data + ((pos - 1) / 2) * elem_size; if (func->less(parent, child)) break; func->swp(parent, child); } } +#define min_heap_push(_heap, _element, _func) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func) + #endif /* _LINUX_MIN_HEAP_H */ -- cgit v1.2.3 From e146683ccff9af2d26b70a9ea4c87f5a86eff0c4 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:47 +0800 Subject: lib min_heap: add min_heap_init() Add min_heap_init() for initializing heap with data, nr, and size. Link: https://lkml.kernel.org/r/20240524152958.919343-6-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 92830f41642a..b384a4ea2afa 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -38,6 +38,21 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs); }; +/* Initialize a min-heap. */ +static __always_inline +void __min_heap_init(min_heap_char *heap, void *data, int size) +{ + heap->nr = 0; + heap->size = size; + if (data) + heap->data = data; + else + heap->data = heap->preallocated; +} + +#define min_heap_init(_heap, _data, _size) \ + __min_heap_init((min_heap_char *)_heap, _data, _size) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, -- cgit v1.2.3 From 0562d54ddc3dc195f338bd8e816dd8ff154f44ad Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:48 +0800 Subject: lib min_heap: add min_heap_peek() Add min_heap_peek() to retrieve a pointer to the smallest element. The pointer is cast to the appropriate type of heap elements. Link: https://lkml.kernel.org/r/20240524152958.919343-7-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index b384a4ea2afa..d9c4ae7ad0cc 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -53,6 +53,16 @@ void __min_heap_init(min_heap_char *heap, void *data, int size) #define min_heap_init(_heap, _data, _size) \ __min_heap_init((min_heap_char *)_heap, _data, _size) +/* Get the minimum element from the heap. */ +static __always_inline +void *__min_heap_peek(struct min_heap_char *heap) +{ + return heap->nr ? heap->data : NULL; +} + +#define min_heap_peek(_heap) \ + (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, -- cgit v1.2.3 From b9d720e65a72c9754faf689e0859a5632853f4bc Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:49 +0800 Subject: lib min_heap: add min_heap_full() Add min_heap_full() which returns a boolean value indicating whether the heap has reached its maximum capacity. Link: https://lkml.kernel.org/r/20240524152958.919343-8-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d9c4ae7ad0cc..f41898c05f5a 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -63,6 +63,16 @@ void *__min_heap_peek(struct min_heap_char *heap) #define min_heap_peek(_heap) \ (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) +/* Check if the heap is full. */ +static __always_inline +bool __min_heap_full(min_heap_char *heap) +{ + return heap->nr == heap->size; +} + +#define min_heap_full(_heap) \ + __min_heap_full((min_heap_char *)_heap) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, -- cgit v1.2.3 From 267607e87599509a6a39a5f7dd3959365e58af27 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:50 +0800 Subject: lib min_heap: add args for min_heap_callbacks Add a third parameter 'args' for the 'less' and 'swp' functions in the 'struct min_heap_callbacks'. This additional parameter allows these comparison and swap functions to handle extra arguments when necessary. Link: https://lkml.kernel.org/r/20240524152958.919343-9-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 51 ++++++++++++++++++++++++------------------------ 1 file changed, 26 insertions(+), 25 deletions(-) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index f41898c05f5a..4acd0f4b3faf 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -34,8 +34,8 @@ typedef DEFINE_MIN_HEAP(char, min_heap_char) min_heap_char; * @swp: Swap elements function. */ struct min_heap_callbacks { - bool (*less)(const void *lhs, const void *rhs); - void (*swp)(void *lhs, void *rhs); + bool (*less)(const void *lhs, const void *rhs, void *args); + void (*swp)(void *lhs, void *rhs, void *args); }; /* Initialize a min-heap. */ @@ -76,7 +76,7 @@ bool __min_heap_full(min_heap_char *heap) /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *left, *right; void *data = heap->data; @@ -89,7 +89,7 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, break; left = data + (i * 2 + 1) * elem_size; right = data + (i * 2 + 2) * elem_size; - i = func->less(left, right) ? i * 2 + 1 : i * 2 + 2; + i = func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2; } /* Special case for the last leaf with no sibling. */ @@ -97,38 +97,38 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, i = i * 2 + 1; /* Backtrack to the correct location. */ - while (i != pos && func->less(root, data + i * elem_size)) + while (i != pos && func->less(root, data + i * elem_size, args)) i = (i - 1) / 2; /* Shift the element into its correct place. */ j = i; while (i != pos) { i = (i - 1) / 2; - func->swp(data + i * elem_size, data + j * elem_size); + func->swp(data + i * elem_size, data + j * elem_size, args); } } -#define min_heapify(_heap, _pos, _func) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func) +#define min_heapify(_heap, _pos, _func, _args) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { int i; for (i = heap->nr / 2 - 1; i >= 0; i--) - __min_heapify(heap, i, elem_size, func); + __min_heapify(heap, i, elem_size, func, args); } -#define min_heapify_all(_heap, _func) \ - __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args) /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline void __min_heap_pop(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *data = heap->data; @@ -138,11 +138,11 @@ void __min_heap_pop(min_heap_char *heap, size_t elem_size, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } -#define min_heap_pop(_heap, _func) \ - __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) +#define min_heap_pop(_heap, _func, _args) \ + __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args) /* * Remove the minimum element and then push the given element. The @@ -152,19 +152,20 @@ void __min_heap_pop(min_heap_char *heap, size_t elem_size, static __always_inline void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, + void *args) { memcpy(heap->data, element, elem_size); - __min_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } -#define min_heap_pop_push(_heap, _element, _func) \ - __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func) +#define min_heap_pop_push(_heap, _element, _func, _args) \ + __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args) /* Push an element on to the heap, O(log2(nr)). */ static __always_inline void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *data = heap->data; void *child, *parent; @@ -182,13 +183,13 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, for (; pos > 0; pos = (pos - 1) / 2) { child = data + (pos * elem_size); parent = data + ((pos - 1) / 2) * elem_size; - if (func->less(parent, child)) + if (func->less(parent, child, args)) break; - func->swp(parent, child); + func->swp(parent, child, args); } } -#define min_heap_push(_heap, _element, _func) \ - __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func) +#define min_heap_push(_heap, _element, _func, _args) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args) #endif /* _LINUX_MIN_HEAP_H */ -- cgit v1.2.3 From eaa0bc7119247942200b9209d40ffd86ace347d4 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:51 +0800 Subject: lib min_heap: add min_heap_sift_up() Add min_heap_sift_up() to sift up the element at index 'idx' in the heap. Link: https://lkml.kernel.org/r/20240524152958.919343-10-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 4acd0f4b3faf..ddd0186afb77 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -111,6 +111,26 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, #define min_heapify(_heap, _pos, _func, _args) \ __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data = heap->data; + size_t parent; + + while (idx) { + parent = (idx - 1) / 2; + if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + break; + func->swp(data + parent * elem_size, data + idx * elem_size, args); + idx = parent; + } +} + +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, -- cgit v1.2.3 From 420f171031207a13c83560b2ebb32ccc3c8ed6df Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:52 +0800 Subject: lib min_heap: add min_heap_del() Add min_heap_del() to delete the element at index 'idx' in the heap. Link: https://lkml.kernel.org/r/20240524152958.919343-11-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index ddd0186afb77..98e838195e7e 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -212,4 +212,28 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, #define min_heap_push(_heap, _element, _func, _args) \ __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args) +/* Remove ith element from the heap, O(log2(nr)). */ +static __always_inline +bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data = heap->data; + + if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) + return false; + + /* Place last element at the root (position 0) and then sift down. */ + heap->nr--; + if (idx == heap->nr) + return true; + func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); + __min_heap_sift_up(heap, elem_size, idx, func, args); + __min_heapify(heap, idx, elem_size, func, args); + + return true; +} + +#define min_heap_del(_heap, _idx, _func, _args) \ + __min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) + #endif /* _LINUX_MIN_HEAP_H */ -- cgit v1.2.3 From 2eb637c649a3d89c5483dc851ce98d56717a36d2 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:53 +0800 Subject: lib min_heap: update min_heap_push() and min_heap_pop() to return bool values Modify the min_heap_push() and min_heap_pop() to return a boolean value. They now return false when the operation fails and true when it succeeds. Link: https://lkml.kernel.org/r/20240524152958.919343-12-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 98e838195e7e..3410a5f907ad 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -147,18 +147,20 @@ void __min_heapify_all(min_heap_char *heap, size_t elem_size, /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void __min_heap_pop(min_heap_char *heap, size_t elem_size, +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) - return; + return false; /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); __min_heapify(heap, 0, elem_size, func, args); + + return true; } #define min_heap_pop(_heap, _func, _args) \ @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, int pos; if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap")) - return; + return false; /* Place at the end of data. */ pos = heap->nr; @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, break; func->swp(parent, child, args); } + + return true; } #define min_heap_push(_heap, _element, _func, _args) \ -- cgit v1.2.3 From bfe3127180418f1b569999954cb653b9926f75ae Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:54 +0800 Subject: lib min_heap: rename min_heapify() to min_heap_sift_down() After adding min_heap_sift_up(), the naming convention has been adjusted to maintain consistency with the min_heap_sift_up(). Consequently, min_heapify() has been renamed to min_heap_sift_down(). Link: https://lkml.kernel.org/CAP-5=fVcBAxt8Mw72=NCJPRJfjDaJcqk4rjbadgouAEAHz_q1A@mail.gmail.com Link: https://lkml.kernel.org/r/20240524152958.919343-13-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 3410a5f907ad..0baee5787247 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -75,7 +75,7 @@ bool __min_heap_full(min_heap_char *heap) /* Sift the element at pos down the heap. */ static __always_inline -void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, +void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *left, *right; @@ -108,8 +108,8 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, } } -#define min_heapify(_heap, _pos, _func, _args) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) +#define min_heap_sift_down(_heap, _pos, _func, _args) \ + __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) /* Sift up ith element from the heap, O(log2(nr)). */ static __always_inline @@ -139,7 +139,7 @@ void __min_heapify_all(min_heap_char *heap, size_t elem_size, int i; for (i = heap->nr / 2 - 1; i >= 0; i--) - __min_heapify(heap, i, elem_size, func, args); + __min_heap_sift_down(heap, i, elem_size, func, args); } #define min_heapify_all(_heap, _func, _args) \ @@ -158,7 +158,7 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_size, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); return true; } @@ -178,7 +178,7 @@ void __min_heap_pop_push(min_heap_char *heap, void *args) { memcpy(heap->data, element, elem_size); - __min_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); } #define min_heap_pop_push(_heap, _element, _func, _args) \ @@ -232,7 +232,7 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, return true; func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); __min_heap_sift_up(heap, elem_size, idx, func, args); - __min_heapify(heap, idx, elem_size, func, args); + __min_heap_sift_down(heap, idx, elem_size, func, args); return true; } -- cgit v1.2.3 From e596930fc78b97b71df80df0fb1cbf2efb9fc6e4 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Fri, 24 May 2024 23:29:55 +0800 Subject: lib min_heap: update min_heap_push() to use min_heap_sift_up() Update min_heap_push() to use min_heap_sift_up() rather than its origin inline version. Link: https://lkml.kernel.org/r/20240524152958.919343-14-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Arnaldo Carvalho de Melo Cc: Bagas Sanjaya Cc: Brian Foster Cc: Ching-Chun (Jim) Huang Cc: Coly Li Cc: Ingo Molnar Cc: Jiri Olsa Cc: Kent Overstreet Cc: Mark Rutland Cc: Matthew Sakai Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/min_heap.h | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) (limited to 'include/linux') diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 0baee5787247..43a7b9dcf15e 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -190,7 +190,6 @@ bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; - void *child, *parent; int pos; if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap")) @@ -202,13 +201,7 @@ bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, heap->nr++; /* Sift child at pos up. */ - for (; pos > 0; pos = (pos - 1) / 2) { - child = data + (pos * elem_size); - parent = data + ((pos - 1) / 2) * elem_size; - if (func->less(parent, child, args)) - break; - func->swp(parent, child, args); - } + __min_heap_sift_up(heap, elem_size, pos, func, args); return true; } -- cgit v1.2.3 From 7c45d8282660cf4ce011d96bf918df50b7481b3c Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 27 May 2024 17:56:44 -0700 Subject: sched: avoid using ilog2() in sched.h indirectly via cpumask.h path includes the ilog2.h header to calculate ilog2(TASK_REPORT_MAX). The following patches drops sched.h dependency on cpumask.h, and to have a successful build, the header has to be included explicitly. sched.h is a frequently included header, and it's better to keep the dependency list as small as possible. So, instead of including ilog2.h for a single BUILD_BUG_ON() check, the same check may be implemented by taking exponent of the other part of equation. Link: https://lkml.kernel.org/r/20240528005648.182376-3-yury.norov@gmail.com Signed-off-by: Yury Norov Cc: Amit Daniel Kachhap Cc: Anna-Maria Behnsen Cc: Christoph Lameter Cc: Daniel Lezcano Cc: Dennis Zhou Cc: Frederic Weisbecker Cc: Johannes Weiner Cc: Juri Lelli Cc: Kees Cook Cc: Mathieu Desnoyers Cc: Paul E. McKenney Cc: Peter Zijlstra Cc: Rafael J. Wysocki Cc: Rasmus Villemoes Cc: Tejun Heo Cc: Thomas Gleixner Cc: Ulf Hansson Cc: Vincent Guittot Cc: Viresh Kumar Cc: Yury Norov Signed-off-by: Andrew Morton --- include/linux/sched.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/linux') diff --git a/include/linux/sched.h b/include/linux/sched.h index 61591ac6eab6..98abb07de149 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1604,7 +1604,7 @@ static inline char task_index_to_char(unsigned int state) { static const char state_char[] = "RSDTtXZPI"; - BUILD_BUG_ON(1 + ilog2(TASK_REPORT_MAX) != sizeof(state_char) - 1); + BUILD_BUG_ON(TASK_REPORT_MAX * 2 != 1 << (sizeof(state_char) - 1)); return state_char[state]; } -- cgit v1.2.3 From eb4faa36d674eed60a522a72a3a40384f4b285d4 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 27 May 2024 17:56:45 -0700 Subject: cpumask: split out include/linux/cpumask_types.h Many core headers, like sched.h, include cpumask.h mostly for struct cpumask and cpumask_var_t. Those are frequently used headers and shouldn't pull more than the bare minimum. Link: https://lkml.kernel.org/r/20240528005648.182376-4-yury.norov@gmail.com Signed-off-by: Yury Norov Cc: Amit Daniel Kachhap Cc: Anna-Maria Behnsen Cc: Christoph Lameter Cc: Daniel Lezcano Cc: Dennis Zhou Cc: Frederic Weisbecker Cc: Johannes Weiner Cc: Juri Lelli Cc: Kees Cook Cc: Mathieu Desnoyers Cc: Paul E. McKenney Cc: Peter Zijlstra Cc: Rafael J. Wysocki Cc: Rasmus Villemoes Cc: Tejun Heo Cc: Thomas Gleixner Cc: Ulf Hansson Cc: Vincent Guittot Cc: Viresh Kumar Signed-off-by: Andrew Morton --- include/linux/cpumask.h | 56 +----------------------------------- include/linux/cpumask_types.h | 66 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 67 insertions(+), 55 deletions(-) create mode 100644 include/linux/cpumask_types.h (limited to 'include/linux') diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h index 23686bed441d..76dca7b86189 100644 --- a/include/linux/cpumask.h +++ b/include/linux/cpumask.h @@ -9,25 +9,13 @@ */ #include #include -#include #include +#include #include #include #include #include -/* Don't assign or return these: may not be this big! */ -typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t; - -/** - * cpumask_bits - get the bits in a cpumask - * @maskp: the struct cpumask * - * - * You should only assume nr_cpu_ids bits of this mask are valid. This is - * a macro so it's const-correct. - */ -#define cpumask_bits(maskp) ((maskp)->bits) - /** * cpumask_pr_args - printf args to output a cpumask * @maskp: cpumask to be printed @@ -922,48 +910,7 @@ static inline unsigned int cpumask_size(void) return bitmap_size(large_cpumask_bits); } -/* - * cpumask_var_t: struct cpumask for stack usage. - * - * Oh, the wicked games we play! In order to make kernel coding a - * little more difficult, we typedef cpumask_var_t to an array or a - * pointer: doing &mask on an array is a noop, so it still works. - * - * i.e. - * cpumask_var_t tmpmask; - * if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) - * return -ENOMEM; - * - * ... use 'tmpmask' like a normal struct cpumask * ... - * - * free_cpumask_var(tmpmask); - * - * - * However, one notable exception is there. alloc_cpumask_var() allocates - * only nr_cpumask_bits bits (in the other hand, real cpumask_t always has - * NR_CPUS bits). Therefore you don't have to dereference cpumask_var_t. - * - * cpumask_var_t tmpmask; - * if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) - * return -ENOMEM; - * - * var = *tmpmask; - * - * This code makes NR_CPUS length memcopy and brings to a memory corruption. - * cpumask_copy() provide safe copy functionality. - * - * Note that there is another evil here: If you define a cpumask_var_t - * as a percpu variable then the way to obtain the address of the cpumask - * structure differently influences what this_cpu_* operation needs to be - * used. Please use this_cpu_cpumask_var_t in those cases. The direct use - * of this_cpu_ptr() or this_cpu_read() will lead to failures when the - * other type of cpumask_var_t implementation is configured. - * - * Please also note that __cpumask_var_read_mostly can be used to declare - * a cpumask_var_t variable itself (not its content) as read mostly. - */ #ifdef CONFIG_CPUMASK_OFFSTACK -typedef struct cpumask *cpumask_var_t; #define this_cpu_cpumask_var_ptr(x) this_cpu_read(x) #define __cpumask_var_read_mostly __read_mostly @@ -1010,7 +957,6 @@ static inline bool cpumask_available(cpumask_var_t mask) } #else -typedef struct cpumask cpumask_var_t[1]; #define this_cpu_cpumask_var_ptr(x) this_cpu_ptr(x) #define __cpumask_var_read_mostly diff --git a/include/linux/cpumask_types.h b/include/linux/cpumask_types.h new file mode 100644 index 000000000000..461ed1b6bcdb --- /dev/null +++ b/include/linux/cpumask_types.h @@ -0,0 +1,66 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_CPUMASK_TYPES_H +#define __LINUX_CPUMASK_TYPES_H + +#include +#include + +/* Don't assign or return these: may not be this big! */ +typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t; + +/** + * cpumask_bits - get the bits in a cpumask + * @maskp: the struct cpumask * + * + * You should only assume nr_cpu_ids bits of this mask are valid. This is + * a macro so it's const-correct. + */ +#define cpumask_bits(maskp) ((maskp)->bits) + +/* + * cpumask_var_t: struct cpumask for stack usage. + * + * Oh, the wicked games we play! In order to make kernel coding a + * little more difficult, we typedef cpumask_var_t to an array or a + * pointer: doing &mask on an array is a noop, so it still works. + * + * i.e. + * cpumask_var_t tmpmask; + * if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) + * return -ENOMEM; + * + * ... use 'tmpmask' like a normal struct cpumask * ... + * + * free_cpumask_var(tmpmask); + * + * + * However, one notable exception is there. alloc_cpumask_var() allocates + * only nr_cpumask_bits bits (in the other hand, real cpumask_t always has + * NR_CPUS bits). Therefore you don't have to dereference cpumask_var_t. + * + * cpumask_var_t tmpmask; + * if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL)) + * return -ENOMEM; + * + * var = *tmpmask; + * + * This code makes NR_CPUS length memcopy and brings to a memory corruption. + * cpumask_copy() provide safe copy functionality. + * + * Note that there is another evil here: If you define a cpumask_var_t + * as a percpu variable then the way to obtain the address of the cpumask + * structure differently influences what this_cpu_* operation needs to be + * used. Please use this_cpu_cpumask_var_t in those cases. The direct use + * of this_cpu_ptr() or this_cpu_read() will lead to failures when the + * other type of cpumask_var_t implementation is configured. + * + * Please also note that __cpumask_var_read_mostly can be used to declare + * a cpumask_var_t variable itself (not its content) as read mostly. + */ +#ifdef CONFIG_CPUMASK_OFFSTACK +typedef struct cpumask *cpumask_var_t; +#else +typedef struct cpumask cpumask_var_t[1]; +#endif /* CONFIG_CPUMASK_OFFSTACK */ + +#endif /* __LINUX_CPUMASK_TYPES_H */ -- cgit v1.2.3 From 361c1f04f3b43b00997b2845c7a9e1d0a9b4c38a Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 27 May 2024 17:56:46 -0700 Subject: sched: drop sched.h dependency on cpumask sched.h needs cpumask.h mostly for types declaration. Now that we have cpumask_types.h, which is a significantly smaller header, we can rely on it. The only exception is UP stub for set_cpus_allowed_ptr(). The function needs to test bit #0 in a @new_mask, which can be trivially opencoded. Link: https://lkml.kernel.org/r/20240528005648.182376-5-yury.norov@gmail.com Signed-off-by: Yury Norov Cc: Amit Daniel Kachhap Cc: Anna-Maria Behnsen Cc: Christoph Lameter Cc: Daniel Lezcano Cc: Dennis Zhou Cc: Frederic Weisbecker Cc: Johannes Weiner Cc: Juri Lelli Cc: Kees Cook Cc: Mathieu Desnoyers Cc: Paul E. McKenney Cc: Peter Zijlstra Cc: Rafael J. Wysocki Cc: Rasmus Villemoes Cc: Tejun Heo Cc: Thomas Gleixner Cc: Ulf Hansson Cc: Vincent Guittot Cc: Viresh Kumar Cc: Yury Norov Signed-off-by: Andrew Morton --- include/linux/sched.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'include/linux') diff --git a/include/linux/sched.h b/include/linux/sched.h index 98abb07de149..f2f907ef1389 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -13,7 +13,7 @@ #include #include #include -#include +#include #include #include @@ -1778,7 +1778,8 @@ static inline void do_set_cpus_allowed(struct task_struct *p, const struct cpuma } static inline int set_cpus_allowed_ptr(struct task_struct *p, const struct cpumask *new_mask) { - if (!cpumask_test_cpu(0, new_mask)) + /* Opencoded cpumask_test_cpu(0, new_mask) to avoid dependency on cpumask.h */ + if ((*cpumask_bits(new_mask) & 1) == 0) return -EINVAL; return 0; } -- cgit v1.2.3 From 7f36688f126ba4a4ec510fa81466b1dacdec97ee Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 27 May 2024 17:56:47 -0700 Subject: cpumask: cleanup core headers inclusion Many core headers include cpumask.h for nothing. Drop it. Link: https://lkml.kernel.org/r/20240528005648.182376-6-yury.norov@gmail.com Signed-off-by: Yury Norov Cc: Amit Daniel Kachhap Cc: Anna-Maria Behnsen Cc: Christoph Lameter Cc: Daniel Lezcano Cc: Dennis Zhou Cc: Frederic Weisbecker Cc: Johannes Weiner Cc: Juri Lelli Cc: Kees Cook Cc: Mathieu Desnoyers Cc: Paul E. McKenney Cc: Peter Zijlstra Cc: Rafael J. Wysocki Cc: Rasmus Villemoes Cc: Tejun Heo Cc: Thomas Gleixner Cc: Ulf Hansson Cc: Vincent Guittot Cc: Viresh Kumar Cc: Yury Norov Signed-off-by: Andrew Morton --- include/linux/cgroup.h | 1 - include/linux/cpu.h | 1 - include/linux/cpu_cooling.h | 1 - include/linux/kernel_stat.h | 1 - include/linux/node.h | 1 - include/linux/percpu.h | 1 - include/linux/profile.h | 1 - include/linux/rcupdate.h | 1 - include/linux/seq_file.h | 1 - include/linux/tracepoint.h | 1 - 10 files changed, 10 deletions(-) (limited to 'include/linux') diff --git a/include/linux/cgroup.h b/include/linux/cgroup.h index 2150ca60394b..c60ba0ab1462 100644 --- a/include/linux/cgroup.h +++ b/include/linux/cgroup.h @@ -10,7 +10,6 @@ */ #include -#include #include #include #include diff --git a/include/linux/cpu.h b/include/linux/cpu.h index 861c3bfc5f17..ea6ac8f98e4a 100644 --- a/include/linux/cpu.h +++ b/include/linux/cpu.h @@ -16,7 +16,6 @@ #include #include -#include #include #include diff --git a/include/linux/cpu_cooling.h b/include/linux/cpu_cooling.h index a3bdc8a98f2c..2c774fb3c091 100644 --- a/include/linux/cpu_cooling.h +++ b/include/linux/cpu_cooling.h @@ -15,7 +15,6 @@ #include #include -#include struct cpufreq_policy; diff --git a/include/linux/kernel_stat.h b/include/linux/kernel_stat.h index 9c042c6384bb..b97ce2df376f 100644 --- a/include/linux/kernel_stat.h +++ b/include/linux/kernel_stat.h @@ -5,7 +5,6 @@ #include #include #include -#include #include #include #include diff --git a/include/linux/node.h b/include/linux/node.h index dfc004e4bee7..9a881c2208b3 100644 --- a/include/linux/node.h +++ b/include/linux/node.h @@ -16,7 +16,6 @@ #define _LINUX_NODE_H_ #include -#include #include /** diff --git a/include/linux/percpu.h b/include/linux/percpu.h index 03053de557cf..4b2047b78b67 100644 --- a/include/linux/percpu.h +++ b/include/linux/percpu.h @@ -6,7 +6,6 @@ #include #include #include -#include #include #include #include diff --git a/include/linux/profile.h b/include/linux/profile.h index 04ae5ebcb637..2fb487f61d12 100644 --- a/include/linux/profile.h +++ b/include/linux/profile.h @@ -4,7 +4,6 @@ #include #include -#include #include #include diff --git a/include/linux/rcupdate.h b/include/linux/rcupdate.h index dfd2399f2cde..fb8ab4618d63 100644 --- a/include/linux/rcupdate.h +++ b/include/linux/rcupdate.h @@ -29,7 +29,6 @@ #include #include #include -#include #include #define ULONG_CMP_GE(a, b) (ULONG_MAX / 2 >= (a) - (b)) diff --git a/include/linux/seq_file.h b/include/linux/seq_file.h index 8bd4fda6e027..2fb266ea69fa 100644 --- a/include/linux/seq_file.h +++ b/include/linux/seq_file.h @@ -7,7 +7,6 @@ #include #include #include -#include #include #include #include diff --git a/include/linux/tracepoint.h b/include/linux/tracepoint.h index 689b6d71590e..6be396bb4297 100644 --- a/include/linux/tracepoint.h +++ b/include/linux/tracepoint.h @@ -16,7 +16,6 @@ #include #include #include -#include #include #include #include -- cgit v1.2.3 From e1b6705bcfb2797ea182e313d5ec4f57fa8571f2 Mon Sep 17 00:00:00 2001 From: Yury Norov Date: Mon, 27 May 2024 17:56:48 -0700 Subject: cpumask: make core headers including cpumask_types.h where possible Now that cpumask types are split out to a separate smaller header, many frequently included core headers may switch to using it. Link: https://lkml.kernel.org/r/20240528005648.182376-7-yury.norov@gmail.com Signed-off-by: Yury Norov Cc: Amit Daniel Kachhap Cc: Anna-Maria Behnsen Cc: Christoph Lameter Cc: Daniel Lezcano Cc: Dennis Zhou Cc: Frederic Weisbecker Cc: Johannes Weiner Cc: Juri Lelli Cc: Kees Cook Cc: Mathieu Desnoyers Cc: Paul E. McKenney Cc: Peter Zijlstra Cc: Rafael J. Wysocki Cc: Rasmus Villemoes Cc: Tejun Heo Cc: Thomas Gleixner Cc: Ulf Hansson Cc: Vincent Guittot Cc: Viresh Kumar Cc: Yury Norov Signed-off-by: Andrew Morton --- include/linux/cacheinfo.h | 2 +- include/linux/clockchips.h | 2 +- include/linux/cpu_rmap.h | 2 +- include/linux/interrupt.h | 2 +- include/linux/irqchip/irq-partition-percpu.h | 2 +- include/linux/msi.h | 2 +- include/linux/pm_domain.h | 2 +- include/linux/stop_machine.h | 2 +- include/linux/torture.h | 2 +- include/linux/workqueue.h | 2 +- 10 files changed, 10 insertions(+), 10 deletions(-) (limited to 'include/linux') diff --git a/include/linux/cacheinfo.h b/include/linux/cacheinfo.h index 2cb15fe4fe12..286db104e054 100644 --- a/include/linux/cacheinfo.h +++ b/include/linux/cacheinfo.h @@ -3,7 +3,7 @@ #define _LINUX_CACHEINFO_H #include -#include +#include #include struct device_node; diff --git a/include/linux/clockchips.h b/include/linux/clockchips.h index 9aac31d856f3..b0df28ddd394 100644 --- a/include/linux/clockchips.h +++ b/include/linux/clockchips.h @@ -12,7 +12,7 @@ #ifdef CONFIG_GENERIC_CLOCKEVENTS # include -# include +# include # include # include diff --git a/include/linux/cpu_rmap.h b/include/linux/cpu_rmap.h index cae324d10965..20b5729903d7 100644 --- a/include/linux/cpu_rmap.h +++ b/include/linux/cpu_rmap.h @@ -7,7 +7,7 @@ * Copyright 2011 Solarflare Communications Inc. */ -#include +#include #include #include #include diff --git a/include/linux/interrupt.h b/include/linux/interrupt.h index 5c9bdd3ffccc..136a55455529 100644 --- a/include/linux/interrupt.h +++ b/include/linux/interrupt.h @@ -5,13 +5,13 @@ #include #include -#include #include #include #include #include #include #include +#include #include #include diff --git a/include/linux/irqchip/irq-partition-percpu.h b/include/linux/irqchip/irq-partition-percpu.h index 2f6ae7551748..b35ee22c278f 100644 --- a/include/linux/irqchip/irq-partition-percpu.h +++ b/include/linux/irqchip/irq-partition-percpu.h @@ -8,7 +8,7 @@ #define __LINUX_IRQCHIP_IRQ_PARTITION_PERCPU_H #include -#include +#include #include struct partition_affinity { diff --git a/include/linux/msi.h b/include/linux/msi.h index dc27cf3903d5..26588da88bdd 100644 --- a/include/linux/msi.h +++ b/include/linux/msi.h @@ -19,7 +19,7 @@ */ #include -#include +#include #include #include #include diff --git a/include/linux/pm_domain.h b/include/linux/pm_domain.h index f24546a3d3db..71e4f0fb8867 100644 --- a/include/linux/pm_domain.h +++ b/include/linux/pm_domain.h @@ -16,7 +16,7 @@ #include #include #include -#include +#include #include /* diff --git a/include/linux/stop_machine.h b/include/linux/stop_machine.h index ea7a74ea7389..3132262a404d 100644 --- a/include/linux/stop_machine.h +++ b/include/linux/stop_machine.h @@ -3,7 +3,7 @@ #define _LINUX_STOP_MACHINE #include -#include +#include #include #include diff --git a/include/linux/torture.h b/include/linux/torture.h index 1541454da03e..c2e979f82f8d 100644 --- a/include/linux/torture.h +++ b/include/linux/torture.h @@ -14,7 +14,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/include/linux/workqueue.h b/include/linux/workqueue.h index fb3993894536..52496f07fba5 100644 --- a/include/linux/workqueue.h +++ b/include/linux/workqueue.h @@ -12,7 +12,7 @@ #include #include #include -#include +#include #include #include -- cgit v1.2.3 From 2f183c68345a26213e5e7f798399bee68d1c4a97 Mon Sep 17 00:00:00 2001 From: Jani Nikula Date: Fri, 31 May 2024 12:04:57 +0300 Subject: kernel/panic: add verbose logging of kernel taints in backtraces With nearly 20 taint flags and respective characters, it's getting a bit difficult to remember what each taint flag character means. Add verbose logging of the set taints in the format: Tainted: [P]=PROPRIETARY_MODULE, [W]=WARN in dump_stack_print_info() when there are taints. Note that the "negative flag" G is not included. Link: https://lkml.kernel.org/r/7321e306166cb2ca2807ab8639e665baa2462e9c.1717146197.git.jani.nikula@intel.com Signed-off-by: Jani Nikula Reviewed-by: Greg Kroah-Hartman Signed-off-by: Andrew Morton --- include/linux/panic.h | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'include/linux') diff --git a/include/linux/panic.h b/include/linux/panic.h index 6717b15e798c..3130e0b5116b 100644 --- a/include/linux/panic.h +++ b/include/linux/panic.h @@ -77,9 +77,10 @@ static inline void set_arch_panic_timeout(int timeout, int arch_default_timeout) #define TAINT_FLAGS_MAX ((1UL << TAINT_FLAGS_COUNT) - 1) struct taint_flag { - char c_true; /* character printed when tainted */ - char c_false; /* character printed when not tainted */ - bool module; /* also show as a per-module taint flag */ + char c_true; /* character printed when tainted */ + char c_false; /* character printed when not tainted */ + bool module; /* also show as a per-module taint flag */ + const char *desc; /* verbose description of the set taint flag */ }; extern const struct taint_flag taint_flags[TAINT_FLAGS_COUNT]; @@ -90,6 +91,7 @@ enum lockdep_ok { }; extern const char *print_tainted(void); +extern const char *print_tainted_verbose(void); extern void add_taint(unsigned flag, enum lockdep_ok); extern int test_taint(unsigned flag); extern unsigned long get_taint(void); -- cgit v1.2.3 From b8c7dd15ceb87e5f37ec1ed7b56c279d98f3eb53 Mon Sep 17 00:00:00 2001 From: Jesse Brandeburg Date: Tue, 11 Jun 2024 17:12:22 -0700 Subject: kernel-wide: fix spelling mistakes like "assocative" -> "associative" There were several instances of the string "assocat" in the kernel, which should have been spelled "associat", with the various endings of -ive, -ed, -ion, and sometimes beginnging with dis-. Add to the spelling dictionary the corrections so that future instances will be caught by checkpatch, and fix the instances found. Originally noticed by accident with a 'git grep socat'. Link: https://lkml.kernel.org/r/20240612001247.356867-1-jesse.brandeburg@intel.com Signed-off-by: Jesse Brandeburg Cc: Randy Dunlap Signed-off-by: Andrew Morton --- include/linux/nvme-fc-driver.h | 2 +- include/linux/soc/apple/rtkit.h | 4 ++-- 2 files changed, 3 insertions(+), 3 deletions(-) (limited to 'include/linux') diff --git a/include/linux/nvme-fc-driver.h b/include/linux/nvme-fc-driver.h index 4109f1bd6128..1177dde77104 100644 --- a/include/linux/nvme-fc-driver.h +++ b/include/linux/nvme-fc-driver.h @@ -620,7 +620,7 @@ enum { * * Structure used between LLDD and nvmet-fc layer to represent the exchange * context for a FC-NVME FCP I/O operation (e.g. a nvme sqe, the sqe-related - * memory transfers, and its assocated cqe transfer). + * memory transfers, and its associated cqe transfer). * * The structure is allocated by the LLDD whenever a FCP CMD IU is received * from the FC link. The address of the structure is passed to the nvmet-fc diff --git a/include/linux/soc/apple/rtkit.h b/include/linux/soc/apple/rtkit.h index 8c9ca857ccf6..c06d17599ae7 100644 --- a/include/linux/soc/apple/rtkit.h +++ b/include/linux/soc/apple/rtkit.h @@ -69,7 +69,7 @@ struct apple_rtkit; * Initializes the internal state required to handle RTKit. This * should usually be called within _probe. * - * @dev: Pointer to the device node this coprocessor is assocated with + * @dev: Pointer to the device node this coprocessor is associated with * @cookie: opaque cookie passed to all functions defined in rtkit_ops * @mbox_name: mailbox name used to communicate with the co-processor * @mbox_idx: mailbox index to be used if mbox_name is NULL @@ -83,7 +83,7 @@ struct apple_rtkit *devm_apple_rtkit_init(struct device *dev, void *cookie, * Non-devm version of devm_apple_rtkit_init. Must be freed with * apple_rtkit_free. * - * @dev: Pointer to the device node this coprocessor is assocated with + * @dev: Pointer to the device node this coprocessor is associated with * @cookie: opaque cookie passed to all functions defined in rtkit_ops * @mbox_name: mailbox name used to communicate with the co-processor * @mbox_idx: mailbox index to be used if mbox_name is NULL -- cgit v1.2.3 From 7c812814e8c34a41bff6fe49987760ffaf8702af Mon Sep 17 00:00:00 2001 From: Alexey Dobriyan Date: Mon, 24 Jun 2024 18:39:49 +0300 Subject: compiler.h: simplify data_race() macro -Wdeclaration-after-statement used since forever required statement expressions to inject __kcsan_disable_current(), __kcsan_enable_current() to mark data race. Now that it is gone, make macro expansion simpler. __unqual_scalar_typeof() is wordy macro b