The patch titled
Subject: lib/list_sort: clarify comparison function requirements in sort_r()
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-list_sort-clarify-comparison-function-requirements-in-sort_r.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-list_sort-clarify-comparison-function-requirements-in-sort_r.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Subject: lib/list_sort: clarify comparison function requirements in sort_r()
Date: Wed, 25 Dec 2024 00:39:27 +0800
Add a detailed explanation in the list_sort() kernel doc comment
specifying that the comparison function must satisfy antisymmetry and
transitivity. These properties are essential for the sorting algorithm to
produce correct results.
Issues have arisen in the past [1][2][3][4] where comparison functions
violated the transitivity property, causing sorting algorithms to fail to
correctly order elements. While these requirements may seem
straightforward, they are commonly misunderstood or overlooked, leading to
bugs. Highlighting these properties in the documentation will help
prevent such mistakes in the future.
Link: https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@xxxxxxxxx [1]
Link: https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@xxxxxxxxx [2]
Link: https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@xxxxxxxxx [3]
Link: https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@xxxxxxxxx [4]
Link: https://lkml.kernel.org/r/20241224163927.2558195-3-visitorckw@xxxxxxxxx
Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
Cc: Ching-Chun (Jim) Huang <jserv@xxxxxxxxxxxxxxxx>
Cc: <chuang@xxxxxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/list_sort.c | 7 +++++++
1 file changed, 7 insertions(+)
--- a/lib/list_sort.c~lib-list_sort-clarify-comparison-function-requirements-in-sort_r
+++ a/lib/list_sort.c
@@ -108,6 +108,13 @@ static void merge_final(void *priv, list
* and list_sort is a stable sort, so it is not necessary to distinguish
* the @a < @b and @a == @b cases.
*
+ * The comparison function must adhere to specific mathematical properties
+ * to ensure correct and stable sorting:
+ * - Antisymmetry: cmp(@a, @b) must return the opposite sign of
+ * cmp(@b, @a).
+ * - Transitivity: if cmp(@a, @b) <= 0 and cmp(@b, @c) <= 0, then
+ * cmp(@a, @c) <= 0.
+ *
* This is compatible with two styles of @cmp function:
* - The traditional style which returns <0 / =0 / >0, or
* - Returning a boolean 0/1.
_
Patches currently in -mm which might be from visitorckw@xxxxxxxxx are
scripts-sorttable-fix-orc_sort_cmp-to-maintain-symmetry-and-transitivity.patch
lib-min_heap-improve-type-safety-in-min_heap-macros-by-using-container_of.patch
lib-test_min_heap-use-inline-min-heap-variants-to-reduce-attack-vector.patch
lib-min_heap-add-brief-introduction-to-min-heap-api.patch
documentation-core-api-min_heap-add-author-information.patch
lib-sort-clarify-comparison-function-requirements-in-sort_r.patch
lib-list_sort-clarify-comparison-function-requirements-in-sort_r.patch
