From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from canpmsgout05.his.huawei.com (canpmsgout05.his.huawei.com [113.46.200.220]) (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 E692F364E9F for ; Tue, 17 Mar 2026 04:05:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=113.46.200.220 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773720365; cv=none; b=BtcC5++w8jUql10pwQrGnkd0fAWO0fpk7vKh5GPVEQThIUfgPA528FzA30gE678nBCqqE7lJAYXwexSWTCfhIuZ1zGHHHp8Ore2cOe3HlwONfPz4+FyyVjsWeoEEBhH1mxvlTl9ny6eyDhZMgvUtxFWAUGVKW1agJu3GBZqwPKo= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1773720365; c=relaxed/simple; bh=L/LegfKko8pdAqT78c78udWnKQE6ACOcG8CmIhVrUOo=; h=Subject:To:CC:References:From:Message-ID:Date:MIME-Version: In-Reply-To:Content-Type; b=Z3g9FSfk7ckLCfgDmcz8WMS6hRBdsRSw2e9b8uFOgd/QS010UYvZMUNHJru1hT+X420oYQK/cvYc37GOiqdq4XZTLPT8STyy/4qw0BD5JiXg4FGs8B8JBSzQJK79KZ5sVyLozPyb5JayehC63JBxvDvDP3/r71V9cWCfATX1vPo= 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=l1VmAPDK; arc=none smtp.client-ip=113.46.200.220 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="l1VmAPDK" dkim-signature: v=1; a=rsa-sha256; d=huawei.com; s=dkim; c=relaxed/relaxed; q=dns/txt; h=From; bh=Ki3YG8bYlRFENAQ4EUe1mXA6kN9upbGqk5j28Sn1tEA=; b=l1VmAPDKdIa+fES1okQG9UmZfK3fsvBiOCivaQI7acc0PAxl7ddemi6nMbZH7x8BZN/MfIDRo DvQVVmKCanNeLDcc8Kk6nNRc8FUnM8NqOytimWnh20V9r/7oSwi4VvFkFSmWeRLCN9oy5aWoUge T2QZad30w3IIHmI367u+Kro= Received: from mail.maildlp.com (unknown [172.19.162.223]) by canpmsgout05.his.huawei.com (SkyGuard) with ESMTPS id 4fZdXR6nYdz12LCj; Tue, 17 Mar 2026 12:00:23 +0800 (CST) Received: from kwepemk500005.china.huawei.com (unknown [7.202.194.90]) by mail.maildlp.com (Postfix) with ESMTPS id 0F32040561; Tue, 17 Mar 2026 12:05:56 +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 12:05:55 +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> From: Zhihao Cheng Message-ID: <7bb23ce1-a0f3-b576-ad79-c9fa746f11ed@huawei.com> Date: Tue, 17 Mar 2026 12:05:54 +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: <20260315193900.218737-1-visitorckw@gmail.com> Content-Type: text/plain; charset="gbk"; format=flowed Content-Transfer-Encoding: 8bit X-ClientProxiedBy: kwepems500002.china.huawei.com (7.221.188.17) To kwepemk500005.china.huawei.com (7.202.194.90) ÔÚ 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 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? > b->prev = tail; > tail = b; > b = b->next;