From nobody Sun Feb 8 21:27:34 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