From nobody Sun Feb 8 06:54:25 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