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