From nobody Sat Feb 7 21:23:49 2026 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) (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 DAC4B8635D for ; Mon, 6 Jan 2025 17:01:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736182884; cv=none; b=RYEBWdTd4ZkBHX1Dag0/SRzaFa4tRcbpBaB0CU7EpnT4G9rkHZv8RyvwJWeh4GO6qv7+BRxndRKmm4ieDgxftVOfKhgGEndnKg9+M9IZkF41QbI5PcqlsKmVFcjQ1FNF4kVPmgqNh6q+F1mWKGAPzwoJIrGeFyYNpqCk4T1QwFw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736182884; c=relaxed/simple; bh=ARXK2RbCFZhLN2d8lVAbdK42jImdmnqDmrmTA9B3G+g=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=XtpMIOc73WCg3z2cuWOUDIJImRd7+qZm/X66wNT5z1vyUKhf4johOqTUAiEHehmVntz7xKOiczoattg2Ajvuo/nIs5cHduYJaEQ0lG8UzR2T0MWaTPFd5FjpQiKj74g/2rxQgc4v4T+DQFBFkMfK/RbM5gKzLwceNn0oBAac/Zw= 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=fYNJGn0W; arc=none smtp.client-ip=209.85.214.169 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="fYNJGn0W" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-2165448243fso10842075ad.1 for ; Mon, 06 Jan 2025 09:01:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1736182882; x=1736787682; 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=p5GocxdX9/caWJH6jymlm78bDbppkrYdymI0vunz080=; b=fYNJGn0Wnag453pZPo8L+82SWEQzCP/EeYj13E3U3bX3WvxfRaKzugEx3hIUr/yoGr kbjlgDZGK0MQlpvp3uHKF3oamxZW7kwwY8fKpL2C5sLy+uo+W6wuBFV+K6T6J+1QWLqZ UqCF9IWQzpfEEmgPbkgNQraNTsBpW71VHjyF1PUfh02fnYjK8PHnPyWn7Y+bsHgIVI5X Ht3hxsO2UZbhOhnrXxoYUnfH2tVRc5vZKDNvakhcV21zqlV/27hJp9CeZupxr3cK8sJp yc7fmrTseR5PiWRZz+vyls5F5WqS6FRaX6H/JUxFWYxLlMAX0btfBiOJVvYCtXZoazs+ SJ8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736182882; x=1736787682; 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=p5GocxdX9/caWJH6jymlm78bDbppkrYdymI0vunz080=; b=NlFU/g3bU8VDDxcJ21q6mclt6xegfWKvdoqSP699hR6hv4ItaK9nvEAShn+hD6lmeC y2WT8nWjwD8kOwMowTqZsWkvZRT1mhfuVpdrGxSdgH183pONEgNx+/pEA4Sbf6ux7JWs SloNwrTifOg5DX/VIDjVkNq/6W663zspMUzxTe+u+iDqMY2WpJdB61zDrNMXygTkeeou n63z/U+7k7g/WrNgtGhZ4WBGfvOxRAJVdjEhCr7tiNXhtIw9bnyqV4kicOjq+Qnw0oa5 ASVVHnem5la65gNOU9yLCfljrRGkO5MDNZ7yLAiVFCvrbv1TOu8/4U1LiQiLTn/kOtB9 DEMw== X-Forwarded-Encrypted: i=1; AJvYcCVCAnAnuJqd8PIYY3qYccoK5c2w8KLwgh8k2Xe9K2vvV/aU77y61HG5eOdLc/q37FCxU7gQXagGQJ6V9LQ=@vger.kernel.org X-Gm-Message-State: AOJu0YybcxSBlS8ivXThXcufH1V4HaMkFOSD0lDtuCbm61yT6hxd4zVH voFtgV/QsfCR4uORD/f26t/Hs9OHvxn6JPbq3D9G9shfHFIzPPaa X-Gm-Gg: ASbGncvahfOrAJDh7HbvOWYLw+Bia3DOc4irGLr0eWLjL9ZVhOJ3wVZMgNQblOYhGwE BJElA4zsK+1bjbAWEXGO68ObvXjI89hce8mqc6GbDdB6+E/gIMU7mBZblpPELEx8BqXsFNhtTdU F9aaH3uX5lP1I1fILgL/2dEIT2F3tI1hmRmHLndfkPfuyBZhAFMFHvQs6ybJF1o+9npnpIlllmZ dDsz6WfpsTnl0JQ968q8s8kG0HpwQ6ZaMImm7c0LDKuftETBVPGJfV3La7OsaPRVstfzRHDBrvA orTOsqvvIwY= X-Google-Smtp-Source: AGHT+IHUP+ywNIPg8RULWX0LbHFBRFWFeKTdRwCR7kID9xkFz/YusRMO9JR5Tv1o8vnrviQx8uY51g== X-Received: by 2002:a17:903:2b10:b0:216:3e87:c9fc with SMTP id d9443c01a7336-219e6e89b91mr929626895ad.5.1736182881901; Mon, 06 Jan 2025 09:01:21 -0800 (PST) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-219dc9cdeabsm285196315ad.125.2025.01.06.09.01.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Jan 2025 09:01:21 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, Chun-Ying Huang , linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v2 1/2] lib/sort: clarify comparison function requirements in sort_r() Date: Tue, 7 Jan 2025 01:01:03 +0800 Message-Id: <20250106170104.3137845-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250106170104.3137845-1-visitorckw@gmail.com> References: <20250106170104.3137845-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..8e73dc55476b 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 Sat Feb 7 21:23:49 2026 Received: from mail-pl1-f172.google.com (mail-pl1-f172.google.com [209.85.214.172]) (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 BBCCC1DED6C for ; Mon, 6 Jan 2025 17:01:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736182887; cv=none; b=ht1FY9bw6B4DVrPPu0wNvP8oXuieI/qsoAIaWecKHR5pKgkRUEnEBE6j4MasE4oV+a13QjOqLlLNkeID9ryCTZY6bqX+AlsxrauHXds9/jT729uCi3RXQ9VGAqfs1DIqFvIzy/MGAk4mZHmbN4a8YDwMO8SjbuEuMC5Jju3gcqg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736182887; c=relaxed/simple; bh=6rsxkiZbuVgPWddL4n1bwADeMkIubFpzSfYlHGLp8fE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=cz7WPeQnXikPQreW8IfiXIXR3AxCQa55Gehk87u8MpxsstR7/4wTKXqOABL/IggA23wHBGEnCE8odWCrbaS1NfEUVPQFpWOQEr26SDPTSAsl2ORROJtkM/gF0EjpLFzhbtOzmnOkghQ/Ffx5qkOIixYTGkv+k7b8dQqgmboOgEA= 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=N9SfoaBP; arc=none smtp.client-ip=209.85.214.172 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="N9SfoaBP" Received: by mail-pl1-f172.google.com with SMTP id d9443c01a7336-2161eb95317so217072675ad.1 for ; Mon, 06 Jan 2025 09:01:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1736182885; x=1736787685; 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=4ECP9e7MKgPEuGg7D+mfSpmsl8he0bfR9I6qT4ycFTc=; b=N9SfoaBPBBFPsKJbXeeBNweiqdmllZP81dg6nWxuCwekVEQHdy3b42KZtYrfYdfBSB WmGR8y47en4wdq8JPcOQWmGLIhswtKw5VcdqSI3krh3I9SLaVkKk7Clh4vjvvfCUbneI rKL/pkHSfgbXZggzwyqN7Lfhd7A4jFfX+cOlblxaNwZg0U0ox0UtH/nCFa1pxgTaSdjv 8jB3soAGw/cYIIGgcr4lSBm9qKXkBYZ9QCMmTWo0mg2CBaTAphXa26Syw6Gmt3Pfmp/O wtHHw1WSV4NRqklg/S5jVLGycLrWY4Be/iuNdE8oKKLSiJQDdaqjtQRrEWkhWrCRtvT4 kpEA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736182885; x=1736787685; 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=4ECP9e7MKgPEuGg7D+mfSpmsl8he0bfR9I6qT4ycFTc=; b=kkKVMMyOadEvp3CB8kmERsQpQOfXoi6Vy3yC70RzrxP9NRq/kT51SbOlGTqeaw13nu 7AlWbOTx9MJXKnPhedRu/c/gTdhvI1CqKmS97NO/n8byjchTv8HJ6F2L2H27IPuk+ib7 Mj6/UDNYE4SecDI0x3YxP8IR2GqIL2kbNUpBmcd5dPLLfhZbg7QIGlDEEefGgDq2lkRH OYlRC+UPlkoxmQmFXWCYRpt00Ucrf/5e9i78YUwXtQuEceZiBecmalNCw75oThndia1v wA9eZQ6yRwN4yhekX+JmFRbkN0smE2GejkGwDxdA07zK0O1ypX5KAvKjjlz8+r0soPJl VNOQ== X-Forwarded-Encrypted: i=1; AJvYcCVYmSWibClFtEKuCDsGAh0RFuY1uUjEx2S7TGiN/FLVIXZcRNBU7G1tNXLxNDlyhGIDw1ULZfzgpCJ1aFg=@vger.kernel.org X-Gm-Message-State: AOJu0YwQnNIz5bUdDenva0lbqAkZPHc7H90Bag1G8CQwJx2WU+G7+phr BVA6WDgzUy+b+ZZbYLHikDnZLee3X9wlXP9x9ORRfF1KOyW1Xq3S5aWE8cwy X-Gm-Gg: ASbGnctx9jM4owaKebjTCJZtyKFSNwhnJf9WnSnuSgHSNu8hRavU21SxblruWdu0O8V A6VPfSHFH1hrYrs1f4v2g9nU6gWHZXEWQ7/f8fPAeTKVRyzPJ5gosdWVKRVIBk7fBPwx8xx3y1z sZ6fH5ZagqQEXBiVKqRFTnbFrt/lhxaPdt2tOqncJNJ6C4Juzy68ONJo672t1AHvLnMMy4HJEXp QBRHafilGEGP1S4zERKkHdc13gcYVy3J1qKtLwNqnI49qoVQEwNPapy8fykNsT7IRFkVkIokeKN EWXLHV8xeSg= X-Google-Smtp-Source: AGHT+IHo0UExJiZ7Zu1vZaNg+DwxJhMI20PE/JRERK02nnWG017sjkSvG5NQk3jVDGPrBKKKCXJGLQ== X-Received: by 2002:a17:902:e88b:b0:216:3436:b87e with SMTP id d9443c01a7336-219e6f14504mr803579385ad.44.1736182884694; Mon, 06 Jan 2025 09:01:24 -0800 (PST) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-219dc9cdeabsm285196315ad.125.2025.01.06.09.01.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 06 Jan 2025 09:01:24 -0800 (PST) From: Kuan-Wei Chiu To: akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, Chun-Ying Huang , linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v2 2/2] lib/list_sort: clarify comparison function requirements in list_sort() Date: Tue, 7 Jan 2025 01:01:04 +0800 Message-Id: <20250106170104.3137845-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250106170104.3137845-1-visitorckw@gmail.com> References: <20250106170104.3137845-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..a310ecb7ccc0 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