Skip to contentSkip to conversation

lib: clarify comparison function requirements

PATCH RESEND Applied Kuan-Wei Chiu 1 participant 3 messages Jan 6, 2025 Library code

lore
Share & tools
lore
#0 lore raw

v2 cover lib: clarify comparison function requirements

Add a detailed explanation in the sort_r/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.

Changes in resend v2:
- Cc @lkml

Changes in v2:
- Fix typo in patch 2: sort_r() -> list_sort()
- Fix htmldocs build warnings reported by Stephen [5]

[5]: https://lore.kernel.org/all/[email protected]/

Kuan-Wei Chiu (2):
lib/sort: clarify comparison function requirements in sort_r() lib/list_sort: clarify comparison function requirements in list_sort()

 lib/list_sort.c | 7 +++++++
 lib/sort.c      | 7 +++++++
 2 files changed, 14 insertions(+)
Signature · 1 line
2.34.1
#1 lore raw

PATCH RESEND v2 1/2 lib/sort: clarify comparison function requirements in sort_r()

Add a detailed explanation in the sort_r() 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.

---
 lib/sort.c | 7 +++++++
 1 file changed, 7 insertions(+)
lib/sort.c +7 -0
index 048b7a6ef967..8e73dc55476b 100644
@@ -200,6 +200,13 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
  * copy (e.g. fix up pointers or auxiliary data), but the built-in swap
  * avoids a slow retpoline and so is significantly faster.
  *
+ * The comparison function must adhere to specific mathematical
+ * properties to ensure correct and stable sorting:
+ * - Antisymmetry: cmp_func(a, b) must return the opposite sign of
+ * cmp_func(b, a).
+ * - Transitivity: if cmp_func(a, b) <= 0 and cmp_func(b, c) <= 0, then
+ * cmp_func(a, c) <= 0.
+ *
  * Sorting time is O(n log n) both on average and worst-case. While
  * quicksort is slightly faster on average, it suffers from exploitable
  * O(n*n) worst-case behavior and extra memory requirements that make
Signature · 1 line
2.34.1
#2 lore raw

PATCH RESEND v2 2/2 lib/list_sort: clarify comparison function requirements in list_sort()

In reply to Kuan-Wei Chiu

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.

---
 lib/list_sort.c | 7 +++++++
 1 file changed, 7 insertions(+)
lib/list_sort.c +7 -0
index 8d3f623536fe..a310ecb7ccc0 100644
@@ -108,6 +108,13 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
  * 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.
Signature · 1 line
2.34.1