linux-kernel - [PATCH] rust: add fast path to `RBTree::find

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <20250625134245.14505-1-work@onurozkan.dev>
Date: Wed, 25 Jun 2025 16:42:45 +0300
From: Onur Özkan <work@...rozkan.dev>
To: rust-for-linux@...r.kernel.org,
	linux-kernel@...r.kernel.org
Cc: ojeda@...nel.org,
	alex.gaynor@...il.com,
	boqun.feng@...il.com,
	gary@...yguo.net,
	bjorn3_gh@...tonmail.com,
	lossin@...nel.org,
	a.hindborg@...nel.org,
	aliceryhl@...gle.com,
	tmgross@...ch.edu,
	dakr@...nel.org,
	mattgilbride@...gle.com,
	wedsonaf@...il.com,
	tamird@...il.com,
	daniel@...lak.dev,
	Onur Özkan <work@...rozkan.dev>
Subject: [PATCH] rust: add fast path to `RBTree::find_mut` for empty tree

Adds a fast path to `RBTree::find_mut` that immediately returns `None`
when the tree is empty.

This should also benefit `RBTree::get_mut`, `RBTree::remove_node` and
`RBTree::remove` functions as they rely on `find_mut` internally.

Signed-off-by: Onur Özkan <work@...rozkan.dev>
---
 rust/kernel/rbtree.rs | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
index 8d978c896747..a9b79b22ea32 100644
--- a/rust/kernel/rbtree.rs
+++ b/rust/kernel/rbtree.rs
@@ -365,6 +365,11 @@ pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {

     /// Used for accessing the given node, if it exists.
     pub fn find_mut(&mut self, key: &K) -> Option<OccupiedEntry<'_, K, V>> {
+        // Fast path: return `None` when tree is empty.
+        if self.root.rb_node.is_null() {
+            return None;
+        }
+
         match self.raw_entry(key) {
             RawEntry::Occupied(entry) => Some(entry),
             RawEntry::Vacant(_entry) => None,
--
2.50.0