linux-kernel - [RESEND PATCH v2 0/2] lib: clarify comparison function requirements

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20250106170104.3137845-1-visitorckw@gmail.com>
Date: Tue,  7 Jan 2025 01:01:02 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: akpm@...ux-foundation.org
Cc: jserv@...s.ncku.edu.tw,
	Chun-Ying Huang <chuang@...nycu.edu.tw>,
	linux-kernel@...r.kernel.org,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [RESEND PATCH v2 0/2] 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.

Link: https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@gmail.com [1]
Link: https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@gmail.com [2]
Link: https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@gmail.com [3]
Link: https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@gmail.com [4]

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/20250106174236.5a74e94e@canb.auug.org.au/

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(+)

-- 
2.34.1