From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from canpmsgout01.his.huawei.com (canpmsgout01.his.huawei.com [113.46.200.216]) (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 113283C3BF0 for ; Tue, 17 Mar 2026 13:22:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=113.46.200.216 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773753754; cv=none; b=gjjHFSThM6I11xzRtkyZgZntnZOTNjzjx/WBwO5Kh0WcRr5k651OzGbys47yM/wOVQMJZmhJ6ME8HQ0jUtE8IsqOrhkHxvDtJ+h3erjNUpIi0Yl9ujokV3bpIj9mSNXTdm2PkfXaQ/vnl6yRUkag8sV2UzqNUmvitXrxwA9UV08= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773753754; c=relaxed/simple; bh=IGNXrSN+7UtnmVF39iXSyXJBjKj5hOrAVOBfsuojDU0=; h=Subject:To:CC:References:From:Message-ID:Date:MIME-Version: In-Reply-To:Content-Type; b=oEfY40axo0DBpsReESQwioHIkwQVd2SzX3tOSCDSe6Jhp3OCKSnt9qwO6mxD3c/HzG7gV/OiEnyzvKOQh6SYePHEhiQfvhOUZOnYTI6TZw+gMQ/e55S+Gbk59dRyMhNJxOeuXvd867L473ehqQcdzMFg4DhXWSuPFRyw6Q0nEnA= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com; spf=pass smtp.mailfrom=huawei.com; dkim=pass (1024-bit key) header.d=huawei.com header.i=@huawei.com header.b=b12nUtLF; arc=none smtp.client-ip=113.46.200.216 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=huawei.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=huawei.com header.i=@huawei.com header.b="b12nUtLF" dkim-signature: v=1; a=rsa-sha256; d=huawei.com; s=dkim; c=relaxed/relaxed; q=dns/txt; h=From; bh=JLvrU3+FPwQzmmiL+5rrPxqvaEOAIBwwHK5WEDPS1uw=; b=b12nUtLFNd1OPn1cSN+yuG7DZiXaH0UFNXSLzTYdkFo/cuzQzeEZ/sk95k3ql7qHibW7rbqJV 6gkSUJM8JKyLdpSOYjAtt3hv7apNN31TRvoodbcZ9yqMiwx6HfOCLz+WRVh6m6ltW2MymyFlSSS 2qDvVRrZ0RWmExuV5r2zu1g= Received: from mail.maildlp.com (unknown [172.19.162.140]) by canpmsgout01.his.huawei.com (SkyGuard) with ESMTPS id 4fZstr1Gpbz1T4Ft; Tue, 17 Mar 2026 21:17:08 +0800 (CST) Received: from kwepemk500005.china.huawei.com (unknown [7.202.194.90]) by mail.maildlp.com (Postfix) with ESMTPS id 3E18620168; Tue, 17 Mar 2026 21:22:28 +0800 (CST) Received: from [10.174.178.46] (10.174.178.46) by kwepemk500005.china.huawei.com (7.202.194.90) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.11; Tue, 17 Mar 2026 21:22:27 +0800 Subject: Re: [PATCH] lib/list_sort: introduce list_sort_nonatomic() and remove dummy cmp() calls To: Kuan-Wei Chiu CC: , , , , , , References: <20260315193900.218737-1-visitorckw@gmail.com> <7bb23ce1-a0f3-b576-ad79-c9fa746f11ed@huawei.com> From: Zhihao Cheng Message-ID: <3fec3dbc-2835-e056-4394-d2dcaae3b80a@huawei.com> Date: Tue, 17 Mar 2026 21:22:26 +0800 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.5.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 8bit X-ClientProxiedBy: kwepems200001.china.huawei.com (7.221.188.67) To kwepemk500005.china.huawei.com (7.202.194.90) 在 2026/3/17 20:32, Kuan-Wei Chiu 写道: > Hi Zhihao, > > On Tue, Mar 17, 2026 at 12:05:54PM +0800, Zhihao Cheng wrote: >> 在 2026/3/16 3:39, 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. >>> >>> To clean up this API while ensuring behavior compatibility: >>> 1. Introduce list_sort_nonatomic(), which explicitly calls >>> cond_resched() internally when count overflows. >>> 2. Remove the dummy cmp(priv, b, b) fallback for standard list_sort(), >>> saving unnecessary function calls and improving determinism. >>> 3. Convert the sole user (fs/ubifs/) to the new API. >>> >>> Note that ubifs still maintains cond_resched() inside its own >>> comparison functions. This patch does not alter the frequency or timing >>> of those scheduling points, guaranteeing no regressions for ubifs, >>> while benefiting all other kernel users. >>> >>> Signed-off-by: Kuan-Wei Chiu >>> --- >>> fs/ubifs/gc.c | 4 +- >>> fs/ubifs/replay.c | 2 +- >>> include/linux/list_sort.h | 3 + >>> lib/list_sort.c | 166 +++++++++++++++++++++----------------- >>> 4 files changed, 100 insertions(+), 75 deletions(-) >> >> lgtm for UBIFS. >> >> Reviewed-by: Zhihao Cheng > > Thanks for your review! > >> >> one small nit below. >> >>> >> [...] >>> diff --git a/include/linux/list_sort.h b/include/linux/list_sort.h >>> index 453105f74e05..f7af29073d48 100644 >>> --- a/include/linux/list_sort.h >>> +++ b/include/linux/list_sort.h >>> @@ -11,4 +11,7 @@ typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, >>> __attribute__((nonnull(2,3))) >>> void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp); >>> + >>> +__attribute__((nonnull(2, 3))) >>> +void list_sort_nonatomic(void *priv, struct list_head *head, list_cmp_func_t cmp); >>> #endif >>> diff --git a/lib/list_sort.c b/lib/list_sort.c >>> index a310ecb7ccc0..788bfc26cf7b 100644 >>> --- a/lib/list_sort.c >>> +++ b/lib/list_sort.c >>> @@ -3,6 +3,7 @@ >>> #include >>> #include >>> #include >>> +#include >>> /* >>> * Returns a list organized in an intermediate format suited >>> @@ -47,7 +48,7 @@ static struct list_head *merge(void *priv, list_cmp_func_t cmp, >>> */ >>> __attribute__((nonnull(2,3,4,5))) >>> static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, >>> - struct list_head *a, struct list_head *b) >>> + struct list_head *a, struct list_head *b, bool may_schedule) >>> { >>> struct list_head *tail = head; >>> u8 count = 0; >>> @@ -79,12 +80,11 @@ static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, >>> /* >>> * If the merge is highly unbalanced (e.g. the input is >>> * already sorted), this loop may run many iterations. >>> - * Continue callbacks to the client even though no >>> - * element comparison is needed, so the client's cmp() >>> - * routine can invoke cond_resched() periodically. >>> + * If may_schedule is true, periodically invoke cond_resched() >>> + * to avoid soft lockups. >>> */ >>> - if (unlikely(!++count)) >>> - cmp(priv, b, b); >>> + if (may_schedule && unlikely(!++count)) >>> + cond_resched(); >> The cond_resched() already has a judgment on whether to schedule out, so the >> 'count' could be removed? > > However, I think keeping the u8 count rate-limiter makes more sense > here due to the overhead difference. > > Evaluating unlikely(!++count) is essentially a single ALU instruction > (register increment) and a zero-flag check, which has virtually zero > cost. On the other hand, cond_resched() is a macro that does much more > than a simple flag check. Depending on the kernel config, it often > invokes __might_resched() (which reads current to check task_struct > states, irq flags, etc.) and makes a call to __cond_resched(). > Evaluating all of this heavy machinery on every single iteration of > such a tight loop would probably introduce noticeable overhead. > > Actually, your comment brings up another thought I wanted to discuss. > > Since we are introducing list_sort_nonatomic(), I wonder if we should > eventually move the cond_resched() out of UBIFS's cmp() functions > entirely and handle it inside list_sort_nonatomic(). > > Right now, because the cmp() callback is inherently invoked at every > step of the merge process, UBIFS ends up evaluating the cond_resched() > macro every 3 or 4 pointer assignments during the main sort. While > UBIFS needs to prevent soft lockups on huge lists, checking for resched > at such a micro-granularity still feels excessive and likely leaves > performance on the table. In my humble opinion, I don't think frequent 'cond_resched' calling will bring observable performance impact, and there are many examples in kernel hotspot paths(eg. blk_mq_prealloc_tag_set_tags/blk_rq_poll_completion/__blk_mq_alloc_rq_maps ...). For list_sort(), I prefer the aim of code cleanup is to make the code more readable. I am neutral on code cleanup for the current implementation of list_sort. > > I didn't make this change in the current patch because I don't have the > proper UBIFS hardware/setup to benchmark the performance difference, > and I wanted to keep the current scheduling frequency exactly the same > to guarantee no regressions. But I'd love to hear your thoughts on > whether reducing the frequency and moving it out of UBIFS's cmp() is > something worth doing in the future. > > Regards, > Kuan-Wei > . >