From nobody Sun Feb 8 05:29:12 2026 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1143F212B25 for ; Tue, 24 Dec 2024 16:39:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1735058379; cv=none; b=ixf4BX4GwZNu/52NlEvyGnUR/53VFCn++njMUw5a5zpTjCzzthQS9P/8wOAmYoKyIaM18MW1aM+n0AJNT8K5Qhbpmb14O6L0Cs9E3tfXc/kTyn3E2YQLOeByFWUQG8ciS42E3CVTT52CUlf0KqTzT5z0JR61yG33JPtPQwp3wrc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1735058379; c=relaxed/simple; bh=UdS43uzHtLeIpQiYeVHsDGldMQ5k0THfUPsFhjydN90=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=WHex3mF+05XvZxNV4aqMWDnyMIF5E59H27cYC6lyUSKejmgGbV8phva6HOIx+9RojJ9yZtd9oBCyT9Pm7VnjWIuqh/MrAN3XqynkQbnKE2jLtvjqPtVgtiVvWOz96962G8n1ao/Fix49gyBeSD1iaPkUXHsnIZ8yRQWsZHtxZBA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ijKG+2an; arc=none smtp.client-ip=209.85.214.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ijKG+2an" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-21654fdd5daso53639815ad.1 for ; Tue, 24 Dec 2024 08:39:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1735058377; x=1735663177; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=mspkc+nMixAEj24MYiP9JK/NmfzlqjidHY/aSCXbhuI=; b=ijKG+2anJDrCh/y3yRFw+eQuDLyjd8C4jjJmsCD9tnBYlDljOJvSkCG1xUZOX6FsDS Mpm8iQZp6RggDgsVOQinc0iY6A2IT1qTpoDYNiwctBRV58+2m2Nds4iiOOCDPQ6kdbpc lm8bBq9LRoWljIApdFyt93uU+0htmud5agU4aEYs1/0DrH0PKGUgdcYKiTSO/CFOFExR /6T2ZCADwFEa37OaNJmoYZm22PPlcMsavDdK5iJZWC9R3T7lFWLJrML1Jw34r4l/fAbF 48Dki9PCo89MrCcORpw1uqqfN1P5anB0rxHjkYyaoJCMVbTNyPTFcqhh1h8SxPoHPRrR WWhg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1735058377; x=1735663177; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mspkc+nMixAEj24MYiP9JK/NmfzlqjidHY/aSCXbhuI=; b=IgOFhqLY2cc27OTJ06EzYR9z68C9WkpY/aVzkNJY4M8kvWI1Y67C/LsxwmZ3U+KJZT 6770liBEig8LT43E18Ofugsznuh61V4aJjzrzD6F6iRotVD68JnItFiFkUSgHAlr+ix4 ZrsbvFMecDRBC6XSWI2T/5lIpFp6TuGAKWUjC0n5VHV0glqThLU1b6e5KZ/AyGnwrwYM EuMP12kBvvtNX7Dt3OHHgfYe5PC0G8ffCo+Uz9VohsKW/Pi6hJYtwNNBG2awAQ4/AnKQ Tm58+EVMrNeYNvwTzY6H5bYLYiTeqBnCY1zKlwId/RyLyTfFLYq1SNVPzRHoCIH6S4Mc 1+sA== X-Forwarded-Encrypted: i=1; AJvYcCWW1R6crZB41km7znd7su7T1QquIzrGSA62JoZv3c1hk9y9bEOp8ICXbptbgyEtY/8WhhYq7tZW8WeYJBU=@vger.kernel.org X-Gm-Message-State: AOJu0YyI1QdcAtWDB9Hg3lEtqgL/xKjxgsC4/7dwPizrRnK865/q4cqM ZEbgFh8ppgjGo0O/0xxTyfTbKZE6FnwQvHSbMPM8aRXsD0HC8dxX X-Gm-Gg: ASbGnctYU0b+3v2/HqePx81jszyHCX3gTDj/8PSb13tCq2uaI4YKCO2w1MLiK7xc7Xj TDwiVF4oMXcgHK2cToWL8Yasfvwrnc7ok6bZBGWTBYFHEn3XEF+FH+aD7gMTHqqgTD+vDLR/M3W TwOSPxVE3WKtYSwr9Zzs6fD4TTzdqP7IxDKeXQ5O1fvbMnh6mhRA8ATCS0CoGeFK3Fd0vx7sKXB i4+eOjV/2U3dJinMdL/rBIyksTf70UCEEr1jGqhOOeHzFlBCPKF9er3SPenmh0IlwCe3PyUoxa/ TswkqgvAzK4= X-Google-Smtp-Source: AGHT+IEVVagDGbs6hz0ud5ZENGgrlj+oOdfUA7DZhoCYQ5Wi2O3fHIW8PKoNidpvwErepOrn1EpQ5A== X-Received: by 2002:a05:6a21:3285:b0:1e1:aad7:d50d with SMTP id adf61e73a8af0-1e5e084b681mr31028154637.46.1735058377306; Tue, 24 Dec 2024 08:39:37 -0800 (PST) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72aad8309f3sm9864895b3a.55.2024.12.24.08.39.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Dec 2024 08:39:36 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, chuang@cs.nycu.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 1/2] lib/sort: clarify comparison function requirements in sort_r() Date: Wed, 25 Dec 2024 00:39:26 +0800 Message-Id: <20241224163927.2558195-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241224163927.2558195-1-visitorckw@gmail.com> References: <20241224163927.2558195-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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. Link: https://lore.kernel.org/lkml/20240701205639.117194-1-visitorckw@gmail= .com [1] Link: https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@gmai= l.com [2] Link: https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@gmai= l.com [3] Link: https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@gmai= l.com [4] Signed-off-by: Kuan-Wei Chiu --- lib/sort.c | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/lib/sort.c b/lib/sort.c index 048b7a6ef967..a5928cf8304e 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -200,6 +200,13 @@ static size_t parent(size_t i, unsigned int lsbit, siz= e_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) <=3D 0 and cmp_func(b, c) <=3D 0, then + * cmp_func(a, c) <=3D 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 --=20 2.34.1 From nobody Sun Feb 8 05:29:12 2026 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 057B9212B10 for ; Tue, 24 Dec 2024 16:39:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1735058385; cv=none; b=o1b9LNyOoF1v9Pqsw8ShJY6ppim4fXvrBthjZ2+LOVPXXWl6GzhB4DHNb2e2VYsWBgrKxAH5c0P9MM+GyUTzCRXPrqREJK+weSs2iTcRf0qYpfG2UNsH47MDkzDAuxD7vzK6QKpaHz6PPjacgdl5iV4lXRmZerRM8lSvTOMd3Ms= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1735058385; c=relaxed/simple; bh=/KJYoLbcWmrtNXeDwPFY5VAhCL7JwC9/xqLKk7w9y+c=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=nQgFTt4aFI5u/LY1J0w6sX6gDpw/Y3tj9Pb7lYHHlhz7dOSC2S62cSNFcyai2gqFl34ABYvSaCjb0ZgB1R3Y7bdG8GlfztAgUpjY2++X6PT4l2hhHZ0mBpZhlzeajHIuhoiC+kawExfAYq022DhYF2gmX5QaUfKbeLY1jt24JBo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=kkAriDP1; arc=none smtp.client-ip=209.85.214.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kkAriDP1" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-216401de828so53017955ad.3 for ; Tue, 24 Dec 2024 08:39:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1735058383; x=1735663183; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=UEr0qMKV3FX0T0y+NgsinS2HMvbc/cq4bUQfpuAAM5Y=; b=kkAriDP1sUxcTfQjd11F1Ugzy8G64wlkXKW4ShbONhgfn2Kh4VQuZVUQG3U/wLmztc 8lcIsmp9huobLg0D4eVZlaegX9Opag9ouE+kpvbYXErbVnsuIK856s1deeIacNB/nhwu qdVk79E02W2VYfpesUvsDdUTrSlT0zfnJRntTmHEeYF2stBX0Jjv7CvXNyjJOY9CoSE4 6py0bgT+321i5S8JF32ry5gttmAQaCU387qX3zjtfW+SczeKd6xXQYfX+A2hD3mcZQcc xDnymBcPDuqN879BNnZQ14vZJtW8FYGppy11gEus++BeahPyeBMcdy/GKhNXxkhWN3x4 0J8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1735058383; x=1735663183; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=UEr0qMKV3FX0T0y+NgsinS2HMvbc/cq4bUQfpuAAM5Y=; b=oXZjtMdUnOmA7M3lO8tE8Eqr9wSAO2pN3NFtu+uw0af9Uo0jhEZ4mAK8T+UIY+S8WM 6fKfFRLcDoTBtyJYHrkB2vYpVGV0eYUjUnzhKUOSSDjTPyWOZgS6xLORuIXlvisFsBb7 tujtBaFij0Lp3/8I8MAUX2QvjdlmRNlqG/Meo+RpHrR1Qu8+Jl+A4DD+K6LGYfQqFmMq fBlEPfsB1qcR2r0EGSg/S52xDgF9MUiQZ4NdMZ2fNnTS5T65HCKP2dcwP6hteamLoPDe XgR8Ji7b/3ts/7hKbKt29aFwmxxBqEj14MB8e/mAeMtsbjRCjiyawL43o0yVAanh+zmR VJlg== X-Forwarded-Encrypted: i=1; AJvYcCXGFyFnWJ4pxEosb5CNRO0BA4hCLUBT8XLOEKq9HX21244WOcRZ+f/j87BSS1K1pihnOH4xK1GmXwGFFMk=@vger.kernel.org X-Gm-Message-State: AOJu0YztsRAR/eVtIncpywEh+aU1p7ce2CyeSlP3FT91t7km/OlsUkQ9 5GXHRJbHTpBObuDM5iYZkqX++IldFQeS2CjquWGvv1N2v8b6a5yXve5WTL4O X-Gm-Gg: ASbGncupXmprP6ZgGnfABz/oi8nTqAhGnsybHdDZ2Ve3zFlYGBZMeXnx8cz+Oa6LdPd rZHxcB2rrpJVthLsB/mELJ9GKrBYj+J8UiyD86AMn8TAYbua1tE4YFcdAf+vy4d5ZkvkNHCeAel NNMQGT4sy39DrWsvXFTp8YKXbR0ZCvSweflhMU36rhNdemub8q9MQZzm+pUC3kbVziQ+2cpWYmf 2R5uMHr+5gpfny9P7ER8LRpNDftfNaTjXGntKgw8pYQAQvoxbLMaiFGnT22lCefbKqV84Jv4MSy B2t3RyWfv4A= X-Google-Smtp-Source: AGHT+IFyqjbqTtyxKc3SKZqNmzrucNS0pQtB+NxdIjTZJsC7odX0nLdgAybrWdhoGE/0DwbRc+HbUg== X-Received: by 2002:a05:6a21:7e8a:b0:1e1:ae9a:6316 with SMTP id adf61e73a8af0-1e606dfe621mr12676693637.35.1735058383152; Tue, 24 Dec 2024 08:39:43 -0800 (PST) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72aad8309f3sm9864895b3a.55.2024.12.24.08.39.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Dec 2024 08:39:42 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, chuang@cs.nycu.edu.tw, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 2/2] lib/list_sort: clarify comparison function requirements in sort_r() Date: Wed, 25 Dec 2024 00:39:27 +0800 Message-Id: <20241224163927.2558195-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241224163927.2558195-1-visitorckw@gmail.com> References: <20241224163927.2558195-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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@gmail= .com [1] Link: https://lore.kernel.org/lkml/20241203202228.1274403-1-visitorckw@gmai= l.com [2] Link: https://lore.kernel.org/lkml/20241209134226.1939163-1-visitorckw@gmai= l.com [3] Link: https://lore.kernel.org/lkml/20241209145728.1975311-1-visitorckw@gmai= l.com [4] Signed-off-by: Kuan-Wei Chiu --- lib/list_sort.c | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/lib/list_sort.c b/lib/list_sort.c index 8d3f623536fe..fa1bc5fe5a3d 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -108,6 +108,13 @@ static void merge_final(void *priv, list_cmp_func_t cm= p, struct list_head *head, * and list_sort is a stable sort, so it is not necessary to distinguish * the @a < @b and @a =3D=3D @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) <=3D 0 and cmp(@b, @c) <=3D 0, then + * cmp(@a, @c) <=3D 0. + * * This is compatible with two styles of @cmp function: * - The traditional style which returns <0 / =3D0 / >0, or * - Returning a boolean 0/1. --=20 2.34.1