From nobody Sat Apr 4 04:43:37 2026 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) (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 A09273E0234 for ; Fri, 20 Mar 2026 18:10:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774030207; cv=none; b=DF+Pn/GBVsR1Qpwh/M39Cf/M2o8gDOCG3wr+w2zY7/cnW4sKYfgB035+rtKVQxhxnnwp4ZxIOwGvAOkO1qTuB2VElvXVVxoVaHtM+Ad6fDdHAIwyKVvfYldIdVEkFilDbU6CacqoM5ljUHienjabRRYn6FVJSlgexvvVBkH6W1g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774030207; c=relaxed/simple; bh=4T3UH7FQz1EJGTtqgsbLSJUo2WNSefPzYHksvDzpCqk=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=l9a/a1p3tUJxTvQUV2BzrVAynqpzZ/TVV4vEgXq86YoLf67TSePaPJV82Rp42CohTzKGVAP1BlBASTFCzauTX9iWFhu0XBL2FBC0slHineL9AJp9WgSQCWfzPDbcBrIvH8GQPQVQNhuM+qrXcbquVUOVyPPgGz2GEwkwtsRkKfE= 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=fGEA+Zxw; arc=none smtp.client-ip=209.85.210.179 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="fGEA+Zxw" Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-82a67ce6969so1634696b3a.1 for ; Fri, 20 Mar 2026 11:10:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1774030201; x=1774635001; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=psYPSCUI3HObhz8STwDlZrZAaXEuyKQVGNn+8ySckI8=; b=fGEA+ZxwsZMtZiaae9Xdmqijs/Ug+TOjIsuFMt/lSb/xRM6s3Y4QNr5xG2kPiOxQ+8 u8yU/h6UfiRdi1zrohB4P4zjbOouCj0RF1szAPDY1W6AeJ/yiGlmCgxkJFGM99/+MS05 TgFxm37sJ6OF5NUwvsIPNY7haG9PLVlLmWmv4jY76KdDodwRI1yIIeGiuHEk3CFcElV9 KBdqJWExNLLT3J4j/mBplzU+atweoQAwPMXPtVc+tuGaNo6DITBCB0n6cVoJuFnSabMk 6XhRPQ1HxgXjmMfiZWk/CskOtMsY2NFo5tAfFBTut/KjmKzK+u+Ag60qo4fQsI5H46jT uleA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1774030201; x=1774635001; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=psYPSCUI3HObhz8STwDlZrZAaXEuyKQVGNn+8ySckI8=; b=ECuJTmVW9KfVtqpB07arINRwyxe8Eoao/mOlwYyH280+lts5iyKvgiTdFYH1weYqz3 juF4SvPs/xkLcc4hErANDMXYT7CiibwWN8XkBtQp96kiJFe2M7Ij1UfPKIqlQMVEsP+c 6gPYSdVmJi9fC9IxxHQiduJBX3Z0SPl6bfUPQtO7J4GpJmKLhm1V3iSY6cGD0nymbDTp F1VjmtwDVVGW0/R7ONUyoSurJCrtoIdIhGv/wa2J1Z0FnSfA2hT6QUk4r4cuHxNkuj2y CWC+wMCsTSlrRs30jOEqCdy4/phCJ/yWDU1T8yFtzJ4/vFge5rDwZj6pJe1vr5OogHsJ 2puA== X-Forwarded-Encrypted: i=1; AJvYcCWUkrcrEGJO237R4O6Sa3vLdm6A6XtZ0uYIwfR4O5yejNS/2pzVEC4kEqA8TUCOvC7//gn4RYqxV+0PUIU=@vger.kernel.org X-Gm-Message-State: AOJu0Yyo2A+Ih65TrUCVAEUIN9p4onEqA4voayGXVcBl7tSeJ0HaVQAv lJqqY3Vd35e8m6ofghONwoY/nfQdB/M3YneBo8QaZEU9kSoUqn67bYr/ X-Gm-Gg: ATEYQzxeRpqvkV9tyuxhlhQqbxegDz/oGP2PRxrUTabf+iePjnv3u+Y6Y/P6TXEUc05 KegqwegbL/M95QymxhdTWbtDOq3MAZ61ZEuTAtpTPcxZG+kiiF1YcWc6sPxwGLHa1kx0xAl4a24 3Iper7OIGo2sHXXV1PvvplTphSXjrbo9ibLOvCLPTGI0WdXdmKZPyb7mwgxR2gF7NdBnHsWJGmi c31j1jmfMgBG7o9yjcVSfksSg8qI6BWe4dJZStYtbvKsIJvMdlAHsDNqGs3N5hQ1dgsQFrd2a+3 1hFLIb4Rj2eV64fxP3H2mazW9/u7zonr0aYzlEVHVWEiz8bLVQMTJ0LL3eTjBu8FsN+/q7S+U65 ZdQdA03XNDilhpvGeBjmcce43kB8K4owkt6lG7Dc5aF9pmIXKuzSTb4RjHWExDfQHjfAiuU+jbb hogBk6p+lWnL40GHtXBpQpmpqZ1tjX/S7pyn6Rz5F0Z/2FyBGirLTvLT5Pg1gvVC2+KqVEmX8SL iR3EOKdl17TCKNKzTjYQWSO4KDKeG3bw7nAXCU= X-Received: by 2002:a05:6a00:3e07:b0:829:7d31:dd9a with SMTP id d2e1a72fcca58-82a8c335460mr3681559b3a.51.1774030200703; Fri, 20 Mar 2026 11:10:00 -0700 (PDT) Received: from visitorckw-work01.c.googlers.com.com (100.130.194.35.bc.googleusercontent.com. [35.194.130.100]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-82b040d7e56sm2582318b3a.40.2026.03.20.11.09.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Mar 2026 11:10:00 -0700 (PDT) From: Kuan-Wei Chiu To: richard@nod.at, akpm@linux-foundation.org Cc: chengzhihao1@huawei.com, hch@infradead.org, jserv@ccns.ncku.edu.tw, eleanor15x@gmail.com, marscheng@google.com, linux-mtd@lists.infradead.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v3 1/2] ubifs: Remove unnecessary cond_resched() from list_sort() compare Date: Fri, 20 Mar 2026 18:09:37 +0000 Message-ID: <20260320180938.1827148-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.53.0.959.g497ff81fa9-goog In-Reply-To: <20260320180938.1827148-1-visitorckw@gmail.com> References: <20260320180938.1827148-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Historically, UBIFS embedded cond_resched() calls inside its list_sort() comparison callbacks (data_nodes_cmp, nondata_nodes_cmp, and replay_entries_cmp) to prevent soft lockups when sorting long lists. However, further inspection by Richard Weinberger reveals that these compare functions are extremely lightweight and do not perform any blocking MTD I/O. Furthermore, the lists being sorted are strictly bounded in size: - In the GC case, the list contains at most the number of nodes that fit into a single LEB. - In the replay case, the list spans across a few LEBs from the UBIFS journal, amounting to at most a few thousand elements. Since the compare functions are called a few thousand times at most, the overhead of frequent scheduling points is unjustified. Removing the cond_resched() calls simplifies the comparison logic and reduces unnecessary context switch checks during the sort. Signed-off-by: Kuan-Wei Chiu Acked-by: Richard Weinberger Reviewed-by: Zhihao Cheng --- fs/ubifs/gc.c | 2 -- fs/ubifs/replay.c | 1 - 2 files changed, 3 deletions(-) diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c index 0bf08b7755b8..933c79b5cd6b 100644 --- a/fs/ubifs/gc.c +++ b/fs/ubifs/gc.c @@ -109,7 +109,6 @@ static int data_nodes_cmp(void *priv, const struct list= _head *a, struct ubifs_info *c =3D priv; struct ubifs_scan_node *sa, *sb; =20 - cond_resched(); if (a =3D=3D b) return 0; =20 @@ -153,7 +152,6 @@ static int nondata_nodes_cmp(void *priv, const struct l= ist_head *a, struct ubifs_info *c =3D priv; struct ubifs_scan_node *sa, *sb; =20 - cond_resched(); if (a =3D=3D b) return 0; =20 diff --git a/fs/ubifs/replay.c b/fs/ubifs/replay.c index a9a568f4a868..263045e05cf1 100644 --- a/fs/ubifs/replay.c +++ b/fs/ubifs/replay.c @@ -305,7 +305,6 @@ static int replay_entries_cmp(void *priv, const struct = list_head *a, struct ubifs_info *c =3D priv; struct replay_entry *ra, *rb; =20 - cond_resched(); if (a =3D=3D b) return 0; =20 --=20 2.53.0.959.g497ff81fa9-goog From nobody Sat Apr 4 04:43:37 2026 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) (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 1BD1C3DEFF2 for ; Fri, 20 Mar 2026 18:10:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774030210; cv=none; b=Qtmfl6OFtU2Fnrl2v6fQp5/xKUckmmWtVkluZEG5WZnMgiW0s/MVZ1NNvAIgFhsUqr+fQSWprFWrAu5AK4ERIOqkfXnTLy3E6dFOhYEu3kaUaYW8m3gbpBEAc6B5tRhtbl/C+qoUtw2XcVLjHfAUcDD2ybjgiuBsZTMMb0VPhFg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774030210; c=relaxed/simple; bh=QLhWqOPHfOFL/nrkycXFnDQr+Ve6lbu6MGgYyX8axaI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=XcIdQyDrVAU71SLzrejSU/Ft6RM4cvbNihrdzW6Ylm/VO5YAvmdpVMz5ung94F9nsJfMN8zGq8bZC55jXXqBo3v35yJMYcrgeetWI5bBIkGk2mfFl7yB+lw6NQ0CJv/fcoILj5DZzfhq1vAH6D9naeJioxRCFcd5Aocqo1Nw7fc= 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=Hi6BayeI; arc=none smtp.client-ip=209.85.210.176 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="Hi6BayeI" Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-82985f42664so1580475b3a.0 for ; Fri, 20 Mar 2026 11:10:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1774030204; x=1774635004; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=UMdcBuBMskRutNA8N3biKduuLjw+8mQjfcLCAfh2HNM=; b=Hi6BayeIxxdU+7xUxwLuuTeJviwUVuZQrB70ogsoDRFICTn7Iu4kho7NeTcrjawLeq HaKWHeDgpg28K+TVcWfnxPrYIkqqD1nCPPOS7UNbzNu9Unj3rPLGrXFSUz+ZvED/DsLc Z5PTtO7nIXWzUyuJs602Wa0//eOnYS+TxBh5kmz13kievhwsOddrYHITuEe586dJn+RP 4HA4jtgNhvH8cjUIZvSZQN98hskEfuCRPTPNJ9fpdAAJVH+9ve/EjPCvU6FM2q/WUMBt DX529Z9b/psqczc5ZpRWxaLYFy34OuFGRuZEQz79Xy8KtvgIR972Vhphh9IW9DUoojyr rQ2w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1774030204; x=1774635004; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=UMdcBuBMskRutNA8N3biKduuLjw+8mQjfcLCAfh2HNM=; b=O+JxotCRD1HbCNKpi1C8+WSdSjNoOwDEG65S8BqgjKhgGNPH5iyNeCRDL680MnyaX8 6TZ75CVi0x2Loh6niDO9O89gdzplHW3LzlNJWo/Sy3AFIrb9gkWVZ2UuQ+spPVvS9fY1 kMzk5VRsYWNS4s0xLB+fmlogjFm9sXCyUoZatzI+MfWBMdOYHcEzj2k2SSoyXbhvETqg TLvEw+yGRw2hDNunzwtcYEMoPfLx33R3GAJjn0OHGInow6UGiKB7mbbI0D0CqMpIKEHI cISgznme+ODY5vSSIDmHUfSWjYKHL13sdtwg+jL2WwPwXTvWwT5JavApA3WLBdFrADkc W2ow== X-Forwarded-Encrypted: i=1; AJvYcCVnvxXTHOVs6nyXPMwhLojJaH6NUVcGKEplj9PJCrup7RMkr5VuKkzdaa/v3DNSjrmZTuGDynpipQ9+T3g=@vger.kernel.org X-Gm-Message-State: AOJu0YziP4kTKTdX6KWfBLi6EowbkuwI8+aW7rytiy68NBB7Bc2ydMcm n7WXwFe6eCyMebJ6sUglHUayTocQZaBJev1VzJqYK7FZPfm/Z2BOLdhm X-Gm-Gg: ATEYQzzcuaJGPY8tglhQg39oa5nj33cDmmSGA0NsCmO4uD8j/DszDmNFm9XyoTaARNN cNGqhNvj+jC2kD2nK0Al9mWWVWz2ooueVlRMKnB8UgJap9aWp+5vubphd/soaM4wB8Kq4DQFg4z zmo6Bojzcn7QPBjlMh8YgkJWnFZLYoNG92/88k9/FmivBzeO8BDC7VAziywBCs01A1JzM1H6lBz GNb5BNde0+x2SbYhF9+OZ+YvRaLdodf9jaf4YqvFLUbSDvmWlygPzQlUR2Cuc13J3yIkbz8aBgf b+qs0C7rBYi7hoMBxqh2YBbDB04GkdMpXqSefSpE9imgqNifLzVegtkrW1Qj9p19mLMiZwUyt2n 818oRXhgJ8WmjmDoCs+Xu71xvkR00pA+qQQJOJrLU0e/h1fjUVXvHRv4rrhXXXFBxpli7SCkGlJ cgTTkprNpN/l+itMN5kFBoTcnMqz61n58kE+Fa31ZaMpUB5WHa7nDl/6lh/SBVb+FWzzrbU7yrD zP4zJHbI8rphBeL0vYubbUs9PTs10uJw2fLA9I= X-Received: by 2002:a05:6a00:2d05:b0:82a:6125:728f with SMTP id d2e1a72fcca58-82a8c22de9emr3410942b3a.10.1774030204035; Fri, 20 Mar 2026 11:10:04 -0700 (PDT) Received: from visitorckw-work01.c.googlers.com.com (100.130.194.35.bc.googleusercontent.com. [35.194.130.100]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-82b040d7e56sm2582318b3a.40.2026.03.20.11.10.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Mar 2026 11:10:03 -0700 (PDT) From: Kuan-Wei Chiu To: richard@nod.at, akpm@linux-foundation.org Cc: chengzhihao1@huawei.com, hch@infradead.org, jserv@ccns.ncku.edu.tw, eleanor15x@gmail.com, marscheng@google.com, linux-mtd@lists.infradead.org, linux-kernel@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v3 2/2] lib/list_sort: Remove dummy cmp() calls to speed up merge_final() Date: Fri, 20 Mar 2026 18:09:38 +0000 Message-ID: <20260320180938.1827148-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.53.0.959.g497ff81fa9-goog In-Reply-To: <20260320180938.1827148-1-visitorckw@gmail.com> References: <20260320180938.1827148-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Historically, list_sort() implemented a hack in merge_final(): if (unlikely(!++count)) cmp(priv, b, b); This was introduced 16 years ago in commit 835cc0c8477f ("lib: more scalable list_sort()") so that callers could periodically invoke cond_resched() within their comparison functions when merging highly unbalanced lists. An audit of the kernel tree reveals that fs/ubifs/ was the sole user of this mechanism. Recent discussions and inspections by Richard Weinberger confirm that UBIFS lists are strictly bounded in size (a few thousand elements at most), meaning it does not strictly rely on these dummy callbacks to prevent soft lockups. For the vast majority of list_sort() users (such as block layer IO schedulers and file systems), this hack results in completely wasted function calls. In the worst-case scenario (merging an already sorted list where 'a' is exhausted quickly), it results in approximately (N/2)/256 unnecessary cmp() invocations. Remove the dummy cmp(priv, b, b) fallback from merge_final(). This saves unnecessary function calls, avoids branching overhead in the tight loop, and slightly speeds up the final merge step for all generic list_sort() users. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Christoph Hellwig --- lib/list_sort.c | 9 --------- 1 file changed, 9 deletions(-) diff --git a/lib/list_sort.c b/lib/list_sort.c index a310ecb7ccc0..e8ff17c9b2d0 100644 --- a/lib/list_sort.c +++ b/lib/list_sort.c @@ -76,15 +76,6 @@ static void merge_final(void *priv, list_cmp_func_t cmp,= struct list_head *head, /* Finish linking remainder of list b on to tail */ tail->next =3D b; do { - /* - * 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 (unlikely(!++count)) - cmp(priv, b, b); b->prev =3D tail; tail =3D b; b =3D b->next; --=20 2.53.0.959.g497ff81fa9-goog