Commits · 7abcb84f953df037d40fad66f2109db318dd155b · Kirill Smelkov / linux

25 Jun, 2024 37 commits

lib/plist.c: enforce memory ordering in plist_check_list · 7abcb84f

I Hsin Cheng authored May 26, 2024

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.comSigned-off-by: I Hsin Cheng <richard120310@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

7abcb84f

selftests: introduce additional eventfd test coverage · 87beb669

Wen Yang authored May 27, 2024

Add several new test cases which assert corner cases on the eventfd
mechanism, for example, the supplied buffer is less than 8 bytes,
attempting to write a value that is too large, etc.

	./eventfd_test
	# Starting 9 tests from 1 test cases.
	#  RUN           global.eventfd_check_flag_rdwr ...
	#            OK  global.eventfd_check_flag_rdwr
	ok 1 global.eventfd_check_flag_rdwr
	#  RUN           global.eventfd_check_flag_cloexec ...
	#            OK  global.eventfd_check_flag_cloexec
	ok 2 global.eventfd_check_flag_cloexec
	#  RUN           global.eventfd_check_flag_nonblock ...
	#            OK  global.eventfd_check_flag_nonblock
	ok 3 global.eventfd_check_flag_nonblock
	#  RUN           global.eventfd_chek_flag_cloexec_and_nonblock ...
	#            OK  global.eventfd_chek_flag_cloexec_and_nonblock
	ok 4 global.eventfd_chek_flag_cloexec_and_nonblock
	#  RUN           global.eventfd_check_flag_semaphore ...
	#            OK  global.eventfd_check_flag_semaphore
	ok 5 global.eventfd_check_flag_semaphore
	#  RUN           global.eventfd_check_write ...
	#            OK  global.eventfd_check_write
	ok 6 global.eventfd_check_write
	#  RUN           global.eventfd_check_read ...
	#            OK  global.eventfd_check_read
	ok 7 global.eventfd_check_read
	#  RUN           global.eventfd_check_read_with_nonsemaphore ...
	#            OK  global.eventfd_check_read_with_nonsemaphore
	ok 8 global.eventfd_check_read_with_nonsemaphore
	#  RUN           global.eventfd_check_read_with_semaphore ...
	#            OK  global.eventfd_check_read_with_semaphore
	ok 9 global.eventfd_check_read_with_semaphore
	# PASSED: 9 / 9 tests passed.
	# Totals: pass:9 fail:0 xfail:0 xpass:0 skip:0 error:0

Link: https://lkml.kernel.org/r/20240527000200.5615-1-wen.yang@linux.devSigned-off-by: Wen Yang <wen.yang@linux.dev>
Cc: Shuah Khan <shuah@kernel.org>
Cc: Christian Brauner <brauner@kernel.org>
Cc: Andrei Vagin <avagin@google.com>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Dave Young <dyoung@redhat.com>
Cc: Tim Bird <tim.bird@sony.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

87beb669

percpu_counter: add a cmpxchg-based _add_batch variant · 51d82165

Mateusz Guzik authored May 28, 2024

Interrupt disable/enable trips are quite expensive on x86-64 compared to a
mere cmpxchg (note: no lock prefix!) and percpu counters are used quite
often.

With this change I get a bump of 1% ops/s for negative path lookups,
plugged into will-it-scale:

void testcase(unsigned long long *iterations, unsigned long nr)
{
        while (1) {
                int fd = open("/tmp/nonexistent", O_RDONLY);
                assert(fd == -1);

                (*iterations)++;
        }
}

The win would be higher if it was not for other slowdowns, but one has
to start somewhere.

Link: https://lkml.kernel.org/r/20240528204257.434817-1-mjguzik@gmail.comSigned-off-by: Mateusz Guzik <mjguzik@gmail.com>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
Acked-by: Dennis Zhou <dennis@kernel.org>
Cc: Hugh Dickins <hughd@google.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Vlastimil Babka <vbabka@suse.cz>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

51d82165

selftests/mqueue: fix 5 warnings about signed/unsigned mismatches · 727759d7

John Hubbard authored May 27, 2024

When building with clang, via:

    make LLVM=1 -C tools/testing/selftest

...clang warns about several cases of using a signed integer for the
priority argument to mq_receive(3), which expects an unsigned int.

Fix this by declaring the type as unsigned int in all cases.

Link: https://lkml.kernel.org/r/20240527200835.143682-1-jhubbard@nvidia.comSigned-off-by: John Hubbard <jhubbard@nvidia.com>
Reviewed-by: Muhammad Usama Anjum <usama.anjum@collabora.com>
Reviewed-by: Ryan Roberts <ryan.roberts@arm.com>
Cc: David Hildenbrand <david@redhat.com>
Cc: Muhammad Usama Anjum <usama.anjum@collabora.com>
Cc: SeongJae Park <sj@kernel.org>
Cc: Shuah Khan <shuah@kernel.org>
Cc: Valentin Obst <kernel@valentinobst.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

727759d7

lib/test_sort: add a testcase to ensure code coverage · 54ce43da

Kuan-Wei Chiu authored May 28, 2024

The addition of an if statement in lib/sort to handle the final unsorted 2
or 3 elements is not covered by existing test cases, leading to incomplete
test coverage. To ensure comprehensive testing and maintain 100% code
coverage, add a new testcase for scenarios where the if statement is
triggered.

Since the if statement is only triggered when the array length is odd and
the first element is greater than the second element, a testcase is
created using an array length of TEST_LEN - 1 and a suitable random seed
to maintain full code coverage.

Link: https://lkml.kernel.org/r/20240527203011.1644280-5-visitorckw@gmail.comSigned-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

54ce43da

lib/sort: optimize heapsort for handling final 2 or 3 elements · 41ed7804

Kuan-Wei Chiu authored May 28, 2024

After building the heap, the code continuously pops two elements from the
heap until only 2 or 3 elements remain, at which point it switches back to
a regular heapsort with one element popped at a time. However, to handle
the final 2 or 3 elements, an additional else-if statement in the while
loop was introduced, potentially increasing branch misses. Moreover, when
there are only 2 or 3 elements left, continuing with regular heapify
operations is unnecessary as these cases are simple enough to be handled
with a single comparison and 1 or 2 swaps outside the while loop.

Eliminating the additional else-if statement and directly managing cases
involving 2 or 3 elements outside the loop reduces unnecessary conditional
branches resulting from the numerous loops and conditionals in heapify.

This optimization maintains consistent numbers of comparisons and swaps
for arrays with even lengths while reducing swaps and comparisons for
arrays with odd lengths from 2.5 swaps and 1 comparison to 1.5 swaps and 1
comparison.

Link: https://lkml.kernel.org/r/20240527203011.1644280-4-visitorckw@gmail.comSigned-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

41ed7804

lib/sort: fix outdated comment regarding glibc qsort() · f49ac957

Kuan-Wei Chiu authored May 28, 2024

The existing comment in lib/sort refers to glibc qsort() using quicksort.
However, glibc qsort() no longer uses quicksort; it now uses mergesort and
falls back to heapsort if memory allocation for mergesort fails. This
makes the comment outdated and incorrect.

Update the comment to refer to quicksort in general rather than glibc's
implementation to provide accurate information about the comparisons and
trade-offs without implying an outdated implementation.

Link: https://lkml.kernel.org/r/20240527203011.1644280-3-visitorckw@gmail.comSigned-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

f49ac957

lib/sort: remove unused pr_fmt macro · 85fb11a8

Kuan-Wei Chiu authored May 28, 2024

Patch series "lib/sort: Optimizations and cleanups".

This patch series optimizes the handling of the last 2 or 3 elements in
lib/sort and adds a testcase in lib/test_sort to maintain 100% code
coverage reflecting this change. Additionally, it corrects outdated
descriptions regarding glibc qsort() and removes the unused pr_fmt macro.

This patch (of 4):

The pr_fmt macro is defined but not used in lib/sort.c. Since there are
no pr_* functions printing any messages, the pr_fmt macro is redundant and
can be safely removed.

Link: https://lkml.kernel.org/r/20240527203011.1644280-1-visitorckw@gmail.com
Link: https://lkml.kernel.org/r/20240527203011.1644280-2-visitorckw@gmail.comSigned-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

85fb11a8