From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 3F91CF53D81 for ; Mon, 16 Mar 2026 18:04:20 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References: Message-ID:Subject:Cc:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=WC0FaPfsIR2tHRZqbEyWCBiHBxjxM+ZQLZt9cayLqyM=; b=qmUY65N9fUtCad FrjUmCMi0e1oD6NijOWj5+lxYqMzW1chLmfKioyNKZPlTpy/4eyxNxnkVs9tidDUdaJnfTqi7Uf86 rb/qYXfIghpPmIOmd91goAGMYaL2GEG9ZlJSd+r1HSambtSc9gnY+WO+1oNkBZ6lrenxPIDo8M7mo M9xP4TrkaAWMNJyOLM6ZjRbF/v9liWJ3UmKgb47rMRCIr6x4Es88zlBH1kUhUzyJkDbLfsH+Npxca H4yr7WfKx8uZbnT6puv3IX+LPaTl6NI/Om/9bWwv3YmbvVQg+IG8v2hPtoSq7nYxadssOHv/iLnK6 eWr3ZL6eeR/VlUoVmJWw==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.98.2 #2 (Red Hat Linux)) id 1w2CIa-00000004ehk-0tLL; Mon, 16 Mar 2026 18:04:16 +0000 Received: from mail-pj1-x1033.google.com ([2607:f8b0:4864:20::1033]) by bombadil.infradead.org with esmtps (Exim 4.98.2 #2 (Red Hat Linux)) id 1w2CIY-00000004ehP-0gbQ for linux-mtd@lists.infradead.org; Mon, 16 Mar 2026 18:04:15 +0000 Received: by mail-pj1-x1033.google.com with SMTP id 98e67ed59e1d1-359f35dfef6so2546138a91.2 for ; Mon, 16 Mar 2026 11:04:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1773684253; x=1774289053; darn=lists.infradead.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=dyM/EcdmVPp1vKv4B5C+6NX+2arzvVyB57q7i6wvM7w=; b=b1lFioKTpJPhKycHGR2DHQ/c8gQPZT8CK4YvXwliV+icOyATgPc7mvqOWckwXWCJ/0 0l63AEz7a0e1zsaLIdUSbzEpDrJpRN/vtayLNqmj1LKStIt9ElWFX/CDTD0bWbEAbSMU 4kK4IZsv825jopyG6oeiu/rJ5E2Drq1NoA4dup5xPoyVuhA9G1JqtW9VeigSMuutQITs 5Hj9vjD+deacxCs/2ai1tHyrEPHMIVrcYxns6KeCzr8XekEc/LWgscpWbVev+CHnMnSc WF6qdcPQhJXFyPMeFSfr9AE+fd8RbrF/TyTiyijbCN5080J/no5kzqNhypfRev7eAxqw lzUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1773684253; x=1774289053; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=dyM/EcdmVPp1vKv4B5C+6NX+2arzvVyB57q7i6wvM7w=; b=mRYLtteaji25M1OA5GQd9tUBtPyLBD/Yq8mFvWeb/dkxrhUiBxN2JVLtnryxdbzMn7 5JlnW4nEGj9xTjYcIP6JyX25xQCsNOOpyAckFzSaGeNfiO2Yd2UUFRnPqAfZwpTNezoe v09Ra81ydp+y/xSd521BqS4NO4UPuD8C2va68yeppXcOyvx8tpEIZ9sQigLjo1wv47wu V+lgjnZu75fBEJilyOLRwXSU1jYpZnIJUm2SfKzZwpb3ifXLzW9aD9pQvSNlEQZFU3lb PBxSdL7aGd2S+BrVrWnoYuw90I0mtZy7CC19fdVuOa2YVSFA3S4wW2VIQ/VQE8j2s3zg urEA== X-Forwarded-Encrypted: i=1; AJvYcCWpAEixFwmOhq0ZXXrTySH8d9NBdwyTNO8tmf/YKO4UD2GBTFr0gR2pEQ1m9qxFPjK+2VFC3Xf1v+I=@lists.infradead.org X-Gm-Message-State: AOJu0YyqTi0gIcc3PHZC6RTseaEM0F0AmaafsIaFcS+QBiUd0TABwJpA 0QOip5QTMaw6SWYIKih9qQqRUExnu5YLnTgbXtP1Nbx0BmAVHTiyMGHv X-Gm-Gg: ATEYQzz+uNUpzxJ13cwaQSgGJzEtf7/a68tUU/0dYUNBC952iRt1m+I5lYAScoWZigV ldrV3vIFRaUgQBn6RRJNPPorZtQjNcMlMvqA2B2+NMVpchBtgetF7f2irNpOGb32L6PSbCONIF8 kHjOpRwwxbwgnaQF1gFtb1pndxTTWdzriaBKNtSLvP/0yh7cjr3KJCcSKfgss/7fP83LlSw1XVZ 9YTB4Fo/314xJS1qrHUnCDJ51hLIPB3cn1M1NyDm4vhWNMs0Wa9hVYHaS2KpwXAsSmoUStPptlD /u7nCF3Lcjg1VzlN7948JtMOtchsukbJOuIidFvhvmEjsNxNSuiCaUgZAskJSci1JDU0/b5eWuE oldgvN0Wk5Eeq+mpEe2XpaynKu+431xdhD0ZN06mGIoQoHNeEn/mT/AWJTi7R5nlRhVmiN4/R+U 8FJewolFzBfqemqI9/k+uXn2ExfUMAsb9ULEYljFLtXSmzlg== X-Received: by 2002:a17:90b:394f:b0:340:25f0:a9b with SMTP id 98e67ed59e1d1-35a220aae41mr10992627a91.33.1773684253090; Mon, 16 Mar 2026 11:04:13 -0700 (PDT) Received: from google.com ([2402:7500:a44:85b:ee44:f835:d779:2bcf]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-35b8e1cb560sm3574802a91.1.2026.03.16.11.04.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Mar 2026 11:04:12 -0700 (PDT) Date: Tue, 17 Mar 2026 02:04:07 +0800 From: Kuan-Wei Chiu To: Richard Weinberger Cc: Andrew Morton , chengzhihao1 , jserv@ccns.ncku.edu.tw, eleanor15x@gmail.com, marscheng@google.com, linux-mtd , linux-kernel Subject: Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls Message-ID: References: <20260315193900.218737-1-visitorckw@gmail.com> <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20260316_110414_204589_2735BC34 X-CRM114-Status: GOOD ( 15.26 ) X-BeenThere: linux-mtd@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Linux MTD discussion mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: "linux-mtd" Errors-To: linux-mtd-bounces+linux-mtd=archiver.kernel.org@lists.infradead.org Hi Richard, On Mon, Mar 16, 2026 at 08:25:57AM +0100, Richard Weinberger wrote: > ----- Urspr=FCngliche Mail ----- > > Von: "Kuan-Wei Chiu" > > Historically, list_sort() implemented a hack in merge_final(): > > if (unlikely(!++count)) > > cmp(priv, b, b); > > = > > This was designed specifically so that callers could periodically > > invoke cond_resched() within their comparison functions when merging > > highly unbalanced lists. > > = > > However, an audit of the kernel tree reveals that only fs/ubifs/ relies > > on this mechanism. For the vast majority of list_sort() users (such as > > block layer IO schedulers and file systems), this results in completely > > wasted function calls. In the worst-case scenario (merging an already > > sorted list where 'a' is exhausted quickly), this results in > > approximately (N/2)/256 unnecessary cmp() calls. > = > Why isn't this a problem for other users of list_sort()? > Are the lists they sort guaranteed to be short? > = > Or did nobody test hard enough on slow machines without preempt? ;-) TBH, I don't really have a clear answer to that. I tried to dig into the history. It turns out this mechanism was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()"). The commit message explicitly mentioned both XFS and UBIFS as the intended users for this long-list workaround. However, looking at the tree back then, XFS never actually put a cond_resched() in their cmp() function. It seems UBIFS has been the sole user of this trick ever since. Given that it has been this way for 16 years, it seems other subsystems haven't really encountered any practical issues with it. For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions. Regards, Kuan-Wei ______________________________________________________ Linux MTD discussion mailing list http://lists.infradead.org/mailman/listinfo/linux-mtd/ From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-pj1-f44.google.com (mail-pj1-f44.google.com [209.85.216.44]) (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 DF9AE277C96 for ; Mon, 16 Mar 2026 18:04:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.44 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773684254; cv=none; b=IxcXtxlNNqhllMWQRBuswh3n4bO5CH+2xBhU2ppVNkz3ZxNcYiOUKavlg+tBGiP0DYNpYJmuizN7S7pnCCJrYh+MB5a/JGXUp41oYn9TiTA8jJJ2CH6mvEJWrs4B4bKPI7PVb4jGXji8jhFob31v/QDJ/tCJp7q+KupdU6Mpa+4= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773684254; c=relaxed/simple; bh=c75ErGp9Bcsv1RpF9KBL64PGQk7CNIPbEJj2XHMYsbg=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=j/g+l2acEr+CdTXnaki87TWxrF0odq5ywKqYWQ6bSsgnkIQQPcKznR57YhQOo14Z+h3fNZ4hxmDbL0e2CD5CPkoDqz9uVjMg6Xu44ly0tFVTbehZM3l3Nhq+96iq2YVXNIBb5LqfnKKhR48ECf53TO/zuL5j3RDGiCjpsUOB0B0= 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=k6BLIicC; arc=none smtp.client-ip=209.85.216.44 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="k6BLIicC" Received: by mail-pj1-f44.google.com with SMTP id 98e67ed59e1d1-35a1f3f07ebso1941665a91.3 for ; Mon, 16 Mar 2026 11:04:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1773684253; x=1774289053; darn=vger.kernel.org; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:from:to :cc:subject:date:message-id:reply-to; bh=dyM/EcdmVPp1vKv4B5C+6NX+2arzvVyB57q7i6wvM7w=; b=k6BLIicC014ez1/w7LnMQ2SDahXl3M6A5SMYEqwUIjzaUSESp/Rbie9XFPWLz6wi8/ 5RtI2vDxrIMW7gG57QZKfGAX2kzSxSYzuZkgK/GlyYaaCwxEzj+s9bX/sSW2v1nbpgx4 2xjgBVX11JOq2A9o8vaE0bOHgEnVSNMU+qt526kdxYqDb6A3cr5dLyTEEOhskZwmYxj9 sE1DLov4iNUUIxsmj3hpBibfm7AUG/eX4L95Q3anPYJwYhwoTCqjgvLIrnvXzrzS2prw tOHBI9v6exRSTPXn9d0D8HLur2WtzkvQAWQny4H0sibVk/h3zFPemQM/cuvKjLS8ozfO 0I7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1773684253; x=1774289053; h=in-reply-to:content-transfer-encoding:content-disposition :mime-version:references:message-id:subject:cc:to:from:date:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=dyM/EcdmVPp1vKv4B5C+6NX+2arzvVyB57q7i6wvM7w=; b=gr9bqtKvby6DicKIsameDKHFTr53sHq5shmu//9cq0gtw5O+Qjmb0CTtQCo5360l+N QOAoxiC7ymVZ1EtyuasLAIRnMl8GMul2DoHBXsu8zxQoRskqZTqkCLEkoksSw4eJZOb0 oV6Q1C43SLi03+R6FIGJnQHiNbTLLYpJ5lpsKKVcktddKsmT/IgFRlhwwNNUI4KgDnGU FQ7Py6hwBovlkM1ISwHl76N71lH1GKIPRodbIiFMZxSzcvTSHoQjSjszAQ6Q7UDoNxrj uJe17V97LSCCJEYE7YmHllkZtzcz1G2eHMjYx0Z4fA0jaoCEijjDFsv5+1nR5uShX4rd emtg== X-Forwarded-Encrypted: i=1; AJvYcCXnDj+ZYBsNc60nfhTLBhgZrpC0W3EcvF0GRqX+x3USKw0cnFIZiOhG3dYeJWUXCh82CVPIR5tuwyPNZgc=@vger.kernel.org X-Gm-Message-State: AOJu0Yzu7icYQIgNLDJDaLTFscBTkqhbABoBRKduh8yaVz1y0S5uC+Of GBiIIp7ZcWX6uMDDVdxhgz0e3Uf7OFcRIfR5X1upbn+Sil7m+pDrE/WZX6A+AUMB X-Gm-Gg: ATEYQzzjr48/QSBNyQQUuY4EvwnW3D37vy4gAjXvxl/rHblT37kOgZS01GZue991npQ JUoYATv0GQQk72hb0UEmmSnHtZEJk6+WS+iv9eBBYi1BgmoBGEGl9C8IbkmhjhIqR9fhBDDeZXS KNS97YNLhk67LSofReta505jAwJvCp+iLBoMXG36IfWXFhbsdaypObyVqTLwksMeJkXS3Egt+rH MWfLIbWmP7VcDdZBGSzRXdOfgM/s+Q9VAHCnQU3WJuY2DclDWuoy30FCl0lVSdeAdHUy5n0KPPb +bu8WRUPjxmMy3FCO59QdSxcCcRFqYMu/nlMAt//Y2JUpWripzXz6ZQ2AvFcmud4CslxSiHQMTB e8Y3kzXrWggW9ZdtP+rdAUCb/xdVKmCe7IRHTnHdHfU+h2VM4KW/RS2UexAsQs7AEsBQu9v2f2a W5xQzrspGze76Ty/r+VvxWEDplZghaO1n2puDHKspJTTERBg== X-Received: by 2002:a17:90b:394f:b0:340:25f0:a9b with SMTP id 98e67ed59e1d1-35a220aae41mr10992627a91.33.1773684253090; Mon, 16 Mar 2026 11:04:13 -0700 (PDT) Received: from google.com ([2402:7500:a44:85b:ee44:f835:d779:2bcf]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-35b8e1cb560sm3574802a91.1.2026.03.16.11.04.10 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 16 Mar 2026 11:04:12 -0700 (PDT) Date: Tue, 17 Mar 2026 02:04:07 +0800 From: Kuan-Wei Chiu To: Richard Weinberger Cc: Andrew Morton , chengzhihao1 , jserv@ccns.ncku.edu.tw, eleanor15x@gmail.com, marscheng@google.com, linux-mtd , linux-kernel Subject: Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls Message-ID: References: <20260315193900.218737-1-visitorckw@gmail.com> <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> Hi Richard, On Mon, Mar 16, 2026 at 08:25:57AM +0100, Richard Weinberger wrote: > ----- Ursprüngliche Mail ----- > > Von: "Kuan-Wei Chiu" > > Historically, list_sort() implemented a hack in merge_final(): > > if (unlikely(!++count)) > > cmp(priv, b, b); > > > > This was designed specifically so that callers could periodically > > invoke cond_resched() within their comparison functions when merging > > highly unbalanced lists. > > > > However, an audit of the kernel tree reveals that only fs/ubifs/ relies > > on this mechanism. For the vast majority of list_sort() users (such as > > block layer IO schedulers and file systems), this results in completely > > wasted function calls. In the worst-case scenario (merging an already > > sorted list where 'a' is exhausted quickly), this results in > > approximately (N/2)/256 unnecessary cmp() calls. > > Why isn't this a problem for other users of list_sort()? > Are the lists they sort guaranteed to be short? > > Or did nobody test hard enough on slow machines without preempt? ;-) TBH, I don't really have a clear answer to that. I tried to dig into the history. It turns out this mechanism was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()"). The commit message explicitly mentioned both XFS and UBIFS as the intended users for this long-list workaround. However, looking at the tree back then, XFS never actually put a cond_resched() in their cmp() function. It seems UBIFS has been the sole user of this trick ever since. Given that it has been this way for 16 years, it seems other subsystems haven't really encountered any practical issues with it. For UBIFS, this patch doesn't alter the frequency, timing, or behavior of the cond_resched() calls at all, so I am confident that this won't introduce any regressions. Regards, Kuan-Wei