kernel/linux.git/lib/plist.c, branch v6.19.11

treewide: Update email address

2026-01-11T16:09:11+00:00

In a vain attempt to consolidate the email zoo switch everything to the kernel.org account. Signed-off-by: Thomas Gleixner Signed-off-by: Linus Torvalds

Revert "lib/plist.c: enforce memory ordering in plist_check_list"

2025-11-20T22:03:43+00:00

This reverts commit 7abcb84f953df037d40fad66f2109db318dd155b. The introduction of WRITE_ONCE() calls for the 'prev' and 'next' variables inside plist_check_list() was a misapplication. WRITE_ONCE() is fundamentally a compiler barrier designed to prevent compiler optimizations (like caching or reordering) on shared memory locations. However, the variables 'prev' and 'next' are local, stack-allocated pointers accessed only by the current thread's invocation of the function. Since these pointers are thread-local and are never accessed concurrently, applying WRITE_ONCE() to them is semantically incorrect and unnecessary. Furthermore, the use of WRITE_ONCE() on local variables prevents the compiler from performing standard optimizations, such as keeping these variables cached solely in CPU registers throughout the loop, potentially introducing performance overhead. Restore the conventional C assignment for local loop variables, allowing the compiler to generate optimal code. Link: https://lkml.kernel.org/r/20251113193413.499309-1-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Cc: I Hsin Cheng Cc: Ingo Molnar Signed-off-by: Andrew Morton

lib/plist.c: add shortcut for plist_requeue()

2025-03-17T05:30:47+00:00

In the operation of plist_requeue(), "node" is deleted from the list before queueing it back to the list again, which involves looping to find the tail of same-prio entries. If "node" is the head of same-prio entries which means its prio_list is on the priority list, then "node_next" can be retrieve immediately by the next entry of prio_list, instead of looping nodes on node_list. The shortcut implementation can benefit plist_requeue() running the below test, and the test result is shown in the following table. One can observe from the test result that when the number of nodes of same-prio entries is smaller, then the probability of hitting the shortcut can be bigger, thus the benefit can be more significant. While it tends to behave almost the same for long same-prio entries, since the probability of taking the shortcut is much smaller. ----------------------------------------------------------------------- | Test size | 200 | 400 | 600 | 800 | 1000 | ----------------------------------------------------------------------- | new_plist_requeue | 271521| 1007913| 2148033| 4346792| 12200940| ----------------------------------------------------------------------- | old_plist_requeue | 301395| 1105544| 2488301| 4632980| 12217275| ----------------------------------------------------------------------- The test is done on x86_64 architecture with v6.9 kernel and Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz. Test script( executed in kernel module mode ): int init_module(void) { unsigned int test_data[test_size]; /* Split the list into 10 different priority * , when test_size is larger, the number of * nodes within each priority is larger. */ for (i = 0; i < ARRAY_SIZE(test_data); i++) { test_data[i] = i % 10; } ktime_t start, end, time_elapsed = 0; plist_head_init(&test_head_local); for (i = 0; i < ARRAY_SIZE(test_node_local); i++) { plist_node_init(test_node_local + i, 0); test_node_local[i].prio = test_data[i]; } for (i = 0; i < ARRAY_SIZE(test_node_local); i++) { if (plist_node_empty(test_node_local + i)) { plist_add(test_node_local + i, &test_head_local); } } for (i = 0; i < ARRAY_SIZE(test_node_local); i += 1) { start = ktime_get(); plist_requeue(test_node_local + i, &test_head_local); end = ktime_get(); time_elapsed += (end - start); } pr_info("plist_requeue() elapsed time : %lld, size %d\n", time_elapsed, test_size); return 0; } [akpm@linux-foundation.org: tweak comment and code layout] Link: https://lkml.kernel.org/r/20250119062408.77638-1-richard120310@gmail.com Signed-off-by: I Hsin Cheng Cc: Ching-Chun (Jim) Huang Signed-off-by: Andrew Morton

lib/plist.c: avoid worst case scenario in plist_add

2024-06-25T05:25:10+00:00

Worst case scenario of plist_add() happens when the priority of the inserted plist_node is going to be the largest after the insertion is done. The cost is going to be more significant when the original plist is longer, because the iterator is going to traverse the whole plist to find the correct position to insert the new node. The situation can be avoided by using a reverse iterator at the same time, doing so the maximum possible number of iteration is going to shrink from N to N/2. The proposed change of plist_add pasts the test in lib/plist.c to validate its correctness, also add the worst case scenario test for plist_add() in plist_test(). The worst case test are tested with the size of test_data and test_node growing from 200 to 1000. The result are showned in the following table, in which we can observed that the proposed change of plist_add performs better than the original version, and the difference between these two implementations are more significant with the size of N growing. The random case test [1], and best case test [2] are also provided, with result showing the proposed change performs slightly better in random case test while the original implementation performs slightly better in best case test, while the difference in both test are minor, we can see them as even in those two situations. ----------------------------------------------------------- | Test size | 200 | 400 | 600 | 800 | 1000 | ----------------------------------------------------------- | new_plist_add | 140911| 548681| 1220512| 2048493| 3763755| ----------------------------------------------------------- | old_plist_add | 188198| 774222| 1643547| 3008929| 4947435| ----------------------------------------------------------- Link: https://lkml.kernel.org/r/20240614154603.65203-1-richard120310@gmail.com Signed-off-by: I Hsin Cheng Signed-off-by: Ching-Chun (Jim) Huang Signed-off-by: Andrew Morton

lib/plist.c: enforce memory ordering in plist_check_list

2024-06-25T05:25:04+00:00

There exists an iteration over a plist in plist_check_list(), and memory dependency exists between variables "prev", "next" and "prev->next". As plist is used in the scheduling subsystem, we should guarantee the memory ordering between multiple processors. Using macro "WRITE_ONCE()" can help us to ensure the memory ordering as it was stated in "Documentation/memory-barriers.txt". Link: https://lkml.kernel.org/r/20240526140139.17220-1-richard120310@gmail.com Signed-off-by: I Hsin Cheng Signed-off-by: Andrew Morton

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 10

2019-05-21T09:28:45+00:00

Based on 1 normalized pattern(s): licensed under the fsf s gnu public license v2 or later extracted by the scancode license scanner the SPDX license identifier GPL-2.0-or-later has been chosen to replace the boilerplate/reference in 2 file(s). Signed-off-by: Thomas Gleixner Reviewed-by: Kate Stewart Reviewed-by: Jilayne Lovejoy Reviewed-by: Steve Winslow Reviewed-by: Allison Randal Cc: linux-spdx@vger.kernel.org Link: https://lkml.kernel.org/r/20190519154041.526489261@linutronix.de Signed-off-by: Greg Kroah-Hartman

lib/plist: rename DEBUG_PI_LIST to DEBUG_PLIST

2019-05-15T02:52:49+00:00

This is a lot more appropriate than PI_LIST, which in the kernel one would assume that it has to do with priority-inheritance; which is not -- furthermore futexes make use of plists so this can be even more confusing, albeit the debug nature of the config option. Link: http://lkml.kernel.org/r/20190317185434.1626-1-dave@stgolabs.net Signed-off-by: Davidlohr Bueso Reviewed-by: Andrew Morton Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

sched/headers: Prepare for new header dependencies before moving code to

2017-03-02T07:42:27+00:00

We are going to split out of , which will have to be picked up from other headers and .c files. Create a trivial placeholder file that just maps to to make this patch obviously correct and bisectable. Include the new header in the files that are going to need it. Acked-by: Linus Torvalds Cc: Mike Galbraith Cc: Peter Zijlstra Cc: Thomas Gleixner Cc: linux-kernel@vger.kernel.org Signed-off-by: Ingo Molnar

lib/plist.c: remove redundant include

2015-02-13T02:54:16+00:00

Removing the include of linux/spinlock.h produces byte-identical output for {allno,def}config, and identical objdump -d output for allyesconfig. In the former two cases, more than a 100 lines are eliminated from the generated dependency file. Signed-off-by: Rasmus Villemoes Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds

lib/plist.c: replace pr_debug with printk in plist_test()

2014-06-04T23:54:18+00:00

Replace pr_debug() in lib/plist.c test function plist_test() with printk(KERN_DEBUG ...). Without DEBUG defined, pr_debug() is complied out, but the entire plist_test() function is already inside CONFIG_DEBUG_PI_LIST, so printk should just be used directly. Signed-off-by: Dan Streetman Reviewed-by: Steven Rostedt Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds