From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lithops.sigma-star.at (mailout.nod.at [116.203.167.152]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3D195359703 for ; Mon, 16 Mar 2026 21:49:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=116.203.167.152 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773697760; cv=none; b=RyWSqBXvripFJfKiCl1NdEjZitEUqdwuVIYNfNt7dKa/8s1ndf32PxmFlr2iCuvfhtIY0Ut2GIhLSXPZypiRTGqoiCpFeh0BfYL+oMn0eo+L0JjSyIpplD8OAZ3l0SL/QhAF1pzmKdISXJfzXYPkoEbp4gccZx3PMOdJCalhMWA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773697760; c=relaxed/simple; bh=YhBses4MZ4oILpCmZXYxTP4nJaQBrRAg5r9MbNxdGPs=; h=Date:From:To:Cc:Message-ID:In-Reply-To:References:Subject: MIME-Version:Content-Type; b=OHI896Ln8306NfgsdZ+epin6i4RFUAt+E8j/687GacqqfegkQA1GevPRhuxkJQ5iOoYMbEC/obw0b2Wxcy6mlpoIaWAnyVvVhipSGhaihPsQYLYjaPh9DdSMJjxWygUDr7Rksr/4cyDyStg3JtuCjswiPaTpICm/Ci1ttbhASgE= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=nod.at; spf=fail smtp.mailfrom=nod.at; arc=none smtp.client-ip=116.203.167.152 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=nod.at Authentication-Results: smtp.subspace.kernel.org; spf=fail smtp.mailfrom=nod.at Received: from localhost (localhost [127.0.0.1]) by lithops.sigma-star.at (Postfix) with ESMTP id 5675E2C14A8; Mon, 16 Mar 2026 22:49:17 +0100 (CET) Received: from lithops.sigma-star.at ([127.0.0.1]) by localhost (lithops.sigma-star.at [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id lMfQJfoGz_p9; Mon, 16 Mar 2026 22:49:16 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by lithops.sigma-star.at (Postfix) with ESMTP id C83722C14AA; Mon, 16 Mar 2026 22:49:16 +0100 (CET) Received: from lithops.sigma-star.at ([127.0.0.1]) by localhost (lithops.sigma-star.at [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id sWsIcl4yKtIc; Mon, 16 Mar 2026 22:49:16 +0100 (CET) Received: from lithops.sigma-star.at (lithops.sigma-star.at [195.201.40.130]) by lithops.sigma-star.at (Postfix) with ESMTP id 9E1F62C14A8; Mon, 16 Mar 2026 22:49:16 +0100 (CET) Date: Mon, 16 Mar 2026 22:49:16 +0100 (CET) From: Richard Weinberger To: Kuan-Wei Chiu Cc: Andrew Morton , chengzhihao1 , jserv , eleanor15x , marscheng , linux-mtd , linux-kernel Message-ID: <1993407938.46075.1773697756582.JavaMail.zimbra@nod.at> In-Reply-To: References: <20260315193900.218737-1-visitorckw@gmail.com> <1295583760.42468.1773645957126.JavaMail.zimbra@nod.at> Subject: Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls 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=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailer: Zimbra 8.8.12_GA_3807 (ZimbraWebClient - FF148 (Linux)/8.8.12_GA_3809) Thread-Topic: lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls Thread-Index: 33yhQy0Rw9S3aguU5054bV9ZIJmnVA== ----- Urspr=C3=BCngliche Mail ----- > Von: "Kuan-Wei Chiu" >> > However, an audit of the kernel tree reveals that only fs/ubifs/ relie= s >> > on this mechanism. For the vast majority of list_sort() users (such as >> > block layer IO schedulers and file systems), this results in completel= y >> > 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. >>=20 >> Why isn't this a problem for other users of list_sort()? >> Are the lists they sort guaranteed to be short? >>=20 >> Or did nobody test hard enough on slow machines without preempt? ;-) >=20 > TBH, I don't really have a clear answer to that. >=20 > 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. Traditionally both UBI and UBIFS use cond_resched() heavily, my best guess is because their mostly used on tiny embedded systems where soft lockups are more likely. > 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. Sure. I just want to make sure I understand why UBIFS need special treatment. Thanks, //richard