From nobody Thu Sep 24 14:25:40 2026 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-alma10-1.taild15c8.ts.net [100.103.45.18]) (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 9AB2039F162; Wed, 23 Sep 2026 21:00:47 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=100.103.45.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790197251; cv=none; b=e8LqgbBy1GP8kUCoCv9A6NEmhP3Knncp3WK7SsBKwMT+2aGHJxKIGkubpiFCCxIBXgCVdOAB6Yvj9YmIgLmzgrDWPA8OqW9zfC7UlFMAsqFvvOScTIAogCU579+1aF6Si6qNWiU822j0RT2ejbOiRHlJyZVsC7CpVyoftp/qEW0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790197251; c=relaxed/simple; bh=NDK47QPXsUnm2waVc+jmvrVWOOmbOrAV7ItS22ZH6Po=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=g5CWnkhW9PquGTstLCX0FNvFZWwF71K+r/WevtUUHQRCMZ0ETHccucGHLSTaBYk9LtAH1UYX6snhi56ctX9+2gpVr2wvsdRrDv9N59G3yo9V+LjPeReWgjjWhtSwEeatkv7KcAL1NufDcfLT0LJuy78sm2tC0pCRZcMeFlAdk5M= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=OWRkxxBQ; arc=none smtp.client-ip=100.103.45.18 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="OWRkxxBQ" Received: by smtp.kernel.org (Postfix) with ESMTPSA id C5B3F1F00893; Wed, 23 Sep 2026 21:00:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1790197247; bh=LUaewwcHCpqSdiyCfpM8aPg3NJxasQaB1aP4WCOQP7U=; h=From:Date:Subject:References:In-Reply-To:To:Cc; b=OWRkxxBQqWR6vu9xkRXUcTI7hh272FNCzrrfM6w2E5WhG4FCc5RkgNR6dITKlEmAm Zb1vVou/sXA0FLKy4PdGxl3xbjvIiKhFZvO+pph+dHlb8XnP3uyhRr18Xd1vXzfFKL 3r+ZPLgQ93tPt1+FMKFuAUXqbFr9bkongD1jj3JB7LTuILB6Js3wH0HV3/NvwwrlRy 4iAR1is4vJCqJbsREZCxEA/UKmQmXhH5XP9QazPmzZKZiGawiae1BVgQ5vf9h1Vaj3 d4EnAVYR0hb+Q8coaZwwvdV6cNKTSeg7yjEmraIEuJQPWyXT3nC5/D0pdsRjpHHylc gmI6yJ5BZ32xQ== From: Daniel Gomez Date: Wed, 23 Sep 2026 23:00:27 +0200 Subject: [PATCH 1/3] rust: rxarray: add rust xarray support 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 Message-Id: <20260923-rxarray-next-v1-1-92eedf185649@samsung.com> References: <20260923-rxarray-next-v1-0-92eedf185649@samsung.com> In-Reply-To: <20260923-rxarray-next-v1-0-92eedf185649@samsung.com> To: "Matthew Wilcox (Oracle)" , Miguel Ojeda , Boqun Feng , Gary Guo , =?utf-8?q?Bj=C3=B6rn_Roy_Baron?= , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , Danilo Krummrich , Daniel Almeida , Tamir Duberstein , Alexandre Courbot , =?utf-8?q?Onur_=C3=96zkan?= , Daniel Gomez , Andrew Morton Cc: Julia Lawall , Corinn Tiffany , "Liam R. Howlett" , Philipp Stanner , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Samsung GOST , Daniel Gomez X-Mailer: b4 0.16-dev X-Developer-Signature: v=1; a=ed25519-sha256; t=1790197237; l=60495; i=da.gomez@samsung.com; s=20240621; h=from:subject:message-id; bh=ofgGLcKYp5pWfOmVBhixHxPNEQyJ6GQZTguVlJ5waoM=; b=vVX7T1IeUbLWFcGN1wPU95uPRdod+UQIcDeOFHsdT/SrkEP5iMRmZHl/GPGfvpTeDl3y4bqdq 9Kx8cd0qVnrDYjiXIigF9zKYoBhFW7FvsFrQyavmIFoy0zs2eCS5tv0 X-Developer-Key: i=da.gomez@samsung.com; a=ed25519; pk=BqYk31UHkmv0WZShES6pIZcdmPPGay5LbzifAdZ2Ia4= From: Daniel Gomez Add Rust XArray support. This is the Rust implementation of the XArray lib/xarray.c. As of now, it supports basic functionality: store, load, load_mut and erase. Reviewed-by: Andreas Hindborg Signed-off-by: Daniel Gomez --- MAINTAINERS | 11 + rust/kernel/lib.rs | 1 + rust/kernel/rxarray.rs | 1407 ++++++++++++++++++++++++++++++++++++++++++++= ++++ 3 files changed, 1419 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index c2414447892c2..c40a254c35d3d 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -29681,6 +29681,17 @@ C: https://rust-for-linux.zulipchat.com T: git https://github.com/Rust-for-Linux/linux.git xarray-next F: rust/kernel/xarray.rs =20 +XARRAY [RUST] +M: Daniel Gomez +R: Andreas Hindborg +L: rust-for-linux@vger.kernel.org +S: Supported +W: https://rust-for-linux.com +B: https://github.com/Rust-for-Linux/linux/issues +C: https://rust-for-linux.zulipchat.com +T: git git://git.kernel.org/pub/scm/linux/kernel/git/da.gomez/linux.git rx= array-next +F: rust/kernel/rxarray.rs + XBOX DVD IR REMOTE M: Benjamin Valentin S: Maintained diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 4d5c96ddc49c7..1e3c8d3051e53 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -122,6 +122,7 @@ pub mod rbtree; pub mod regulator; pub mod revocable; +pub mod rxarray; pub mod safety; pub mod scatterlist; pub mod security; diff --git a/rust/kernel/rxarray.rs b/rust/kernel/rxarray.rs new file mode 100644 index 0000000000000..9b939b0147252 --- /dev/null +++ b/rust/kernel/rxarray.rs @@ -0,0 +1,1407 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Rust XArray implementation. +//! +//! This module implements an extensible array (aka XArray) via the [`XArr= ay`] type. See [`XArray4`] +//! and [`XArray6`] for common configurations. +//! +//! The array can hold two types of entries at the same time where each in= dex independently stores +//! either an owned pointer (`T: ForeignOwnable`) or a bounded integer up = to `usize::MAX >> 1` +//! backed by [`Bounded`]. Users insert entries via the [`Entry`] type. Re= ferences to entries in +//! the tree are handled by the [`BorrowedEntry`] and [`BorrowedEntryMut`]= types. +//! +//! # Differences from C XArray +//! +//! The C XArray uses RCU for lock-free reads and an internal spinlock for= writes. This +//! implementation does not provide internal locking. A mutable reference = is required for writes, a +//! shared reference for reads. Locking can be applied externally. RCU sup= port is planned. +//! +//! This implementation allocates during store. `xa_reserve()` and `xas_no= mem()` are not yet +//! supported. +//! +//! C `xa_destroy()` frees only internal nodes; callers must free their ow= n stored values. Dropping +//! [`XArray`] also frees all stored entries. +//! +//! C `xa_mk_value()` issues `WARN_ON` if the value exceeds `LONG_MAX`; th= e left shift overflows, +//! producing a wrong entry. +//! Rust [`Entry::int()`] rejects out-of-range values at compile time via = `Bounded`, and +//! [`Entry::try_int()`] returns [`None`] at runtime. +//! +//! The C XArray grows in depth on demand to be efficient for small indice= s, creating a short tree +//! whenever possible and adding levels as larger indices appear. This imp= lementation always walks +//! the full levels, whatever the largest stored index is. Variable height= is planned. +//! +//! C XArray features like search marks, multi-index entries, advanced API= , etc. are not yet +//! implemented. +//! +//! This implementation aims for full feature parity with the C XArray; an= y gap not covered above is +//! a defect in this list. +//! +//! # Data structure +//! +//! The XArray is a radix tree that maps `usize` indices to [`Entry`] valu= es. Each node holds an +//! array of `SIZE` slots (where `SIZE =3D 1 << SHIFT`), and the tree dept= h is +//! `ceil(usize::BITS / SHIFT)`. Indices are decomposed so that each chunk= indexes a slot in a +//! node at the corresponding level. +//! +//! ```text +//! XArray +//! =E2=94=82 +//! =E2=96=BC +//! =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=90 +//! =E2=94=82 Root Node =E2=94=82 Level = =3D levels-1 +//! =E2=94=82 slots[0..SIZE] =E2=94=82 +//! =E2=94=94=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=98 +//! / | \ +//! =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=98 =E2= =94=82 =E2=94=94=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=90 +//! =E2=96=BC =E2=96=BC = =E2=96=BC +//! =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=90 =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=90 =E2=94=8C=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=90 +//! =E2=94=82 Node =E2=94=82 =E2=94=82 Empty =E2=94= =82 =E2=94=82 Node =E2=94=82 +//! =E2=94=82 slots[0..SIZE] =E2=94=82 =E2=94=94=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=98 = =E2=94=82 slots[0..SIZE] =E2=94=82 +//! =E2=94=94=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=98 =E2=94=94=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=98 +//! / \ | +//! =E2=96=BC =E2=96=BC = =E2=96=BC +//! ... ... =E2=94=8C=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=90 +//! =E2=94=82 Leaf Node = =E2=94=82 Level =3D 0 +//! =E2=94=82 slots[0..SIZE= ] =E2=94=82 +//! =E2=94=94=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=98 +//! / | \ +//! =E2=96=BC =E2=96= =BC =E2=96=BC +//! Entry Empty Entry +//! (Int) (Ptr) +//! ``` +//! +//! Index decomposition for [`XArray6`] (SHIFT=3D6, 64 slots per node, 11 = levels on 64-bit): +//! +//! ```text +//! =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=90 +//! =E2=94=82 index = =E2=94=82 +//! =E2=94=9C=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=AC=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=AC=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=AC=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=AC=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=AC=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=A4 +//! =E2=94=82 level10 =E2=94=82 level 9 =E2=94=82 ... =E2=94= =82 level 2 =E2=94=82 level 1 =E2=94=82 level 0 =E2=94=82 +//! =E2=94=82 [63:60] =E2=94=82 [59:54] =E2=94=82 =E2=94= =82 [17:12] =E2=94=82 [11:6] =E2=94=82 [5:0] =E2=94=82 +//! =E2=94=94=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=B4=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=B4=E2=94=80=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=B4=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=B4=E2=94=80=E2=94=80= =E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=B4=E2= =94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94=80=E2=94= =80=E2=94=98 +//! ``` +//! +//! At each level, the slot offset is: `(index >> (level * SHIFT)) & (SIZE= - 1)`. +//! +//! # C API +//! +//! This implementation does not have a C API yet. When one is added, its = FFI layer must validate +//! at runtime what the Rust API enforces at compile or construction time: +//! +//! - **Int values**: use [`Entry::try_int()`]; reject [`None`] as `-EINVA= L`. C has no [`Bounded`], +//! so the FFI wrapper is the enforcement point. +//! - **Pointers**: validate 4-byte alignment and non-null at runtime. +//! `const_assert!(T::FOREIGN_ALIGN >=3D 4)` only covers Rust callers. +//! - **NULL pointers**: dispatch as erase (`xa_store(NULL) =3D=3D xa_eras= e`) or reserve +//! (`XA_FLAGS_ALLOC`) before reaching [`XArray::store()`]. +//! - **Error entries**: reject `xa_is_err()` values; Rust would misclassi= fy them as node pointers +//! (see `Slot` invariants). + +use crate::{ + alloc::Flags, + fmt, + num::Bounded, + prelude::*, + types::ForeignOwnable, // +}; +use core::{ + marker::PhantomData, + mem, // +}; + +/// Type alias for [`XArray`] with a shift of 4 and 16 slots per node. +pub type XArray4 =3D XArray; + +/// Type alias for [`XArray`] with a shift of 6 and 64 slots per node. +pub type XArray6 =3D XArray; + +/// Type alias for [`Entry::Int`] values. Integers that fit in `usize::BIT= S - 1` bits +/// (`0..=3Dusize::MAX >> 1`). +pub type Value =3D Bounded; + +/// An entry is either an [`Entry::Int`] integer (`0..=3Dusize::MAX >> 1`)= or an owned +/// [`Entry::Pointer`]. +/// +/// Empty slots are represented by [`None`], not a separate variant. +/// +/// Integer values are validated by [`Value`]. Pointer alignment (`T::FORE= IGN_ALIGN >=3D 4`) is a +/// requirement of the slot encoding, enforced at compile time when an [`X= Array`] over `T` is +/// constructed (see the [`XArray`] invariants); [`Entry`] itself carries = no invariants. +pub enum Entry { + /// Integer value (`0..=3Dusize::MAX >> 1`). + Int(Value), + /// Pointer payload. Owned (`T`). + Pointer(T), +} + +impl Entry { + /// Creates an [`Entry::Int`] validated at compile time. + /// + /// Fails to compile if `V > usize::MAX >> 1`. + pub const fn int() -> Self { + Entry::Int(Value::new::()) + } + + /// Creates an [`Entry::Int`] validated at runtime. + /// + /// Returns [`None`] if `v > usize::MAX >> 1`. + pub fn try_int(v: usize) -> Option { + Value::try_new(v).map(Entry::Int) + } +} + +/// A borrowed entry returned by [`XArray::load()`], containing either an = integer or a borrowed +/// pointer. +pub enum BorrowedEntry<'a, T: ForeignOwnable + 'a> { + /// Integer value (`0..=3Dusize::MAX >> 1`). + Int(Value), + /// Pointer payload `T::Borrowed<'_>`. + Pointer(T::Borrowed<'a>), +} + +/// A mutably borrowed entry returned by [`XArray::load_mut()`], containin= g either an integer or a +/// borrowed pointer. +pub enum BorrowedEntryMut<'a, T: ForeignOwnable + 'a> { + /// Integer value (`0..=3Dusize::MAX >> 1`). + Int(Value), + /// Pointer payload `T::BorrowedMut<'_>`. + Pointer(T::BorrowedMut<'a>), +} + +/// The error returned by [`XArray::store()`]. +/// +/// Contains the underlying error and the entry that was not stored. +pub struct StoreError { + /// The error that occurred. + pub error: Error, + /// The entry that was not stored. + pub entry: Entry, +} + +impl fmt::Debug for StoreError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("StoreError") + .field("error", &self.error) + .finish() + } +} + +impl From> for Error { + #[inline] + fn from(value: StoreError) -> Self { + value.error + } +} + +/// An extensible array backed by a radix tree, mapping `usize` indices to= [`Entry`] values. +/// +/// `T` must be a [`ForeignOwnable`] whose `FOREIGN_ALIGN` is at least 4. = The type can be named with +/// any other `T`, but constructing a value of it fails to compile. +/// +/// # Ownership +/// +/// When an [`XArray`] is dropped, all stored [`Entry::Pointer`] entries a= re freed via +/// [`ForeignOwnable::from_foreign()`]. This differs from the C `xa_destro= y()`, which only frees +/// internal nodes and requires callers to free stored pointers themselves= . [`Entry::Int`] entries +/// are encoded integers with no backing allocation and need no cleanup. +/// +/// # Examples +/// +/// ``` +/// use kernel::alloc::{flags, KBox}; +/// use kernel::rxarray::{BorrowedEntry, Entry, XArray6}; +/// +/// let mut xa =3D XArray6::>::new(); +/// assert!(xa.is_empty()); +/// +/// // Store a pointer entry at index 1. +/// let boxed =3D KBox::new(0xbeef_u64, flags::GFP_KERNEL)?; +/// xa.store(1, Entry::Pointer(boxed), flags::GFP_KERNEL)?; +/// match xa.load(1) { +/// Some(BorrowedEntry::Pointer(val)) =3D> assert_eq!(*val, 0xbeef_u64= ), +/// _ =3D> panic!("expected Pointer"), +/// } +/// +/// // Store a value entry at index 0. +/// let old =3D xa.store(0, Entry::int::<0xdead>(), flags::GFP_KERNEL)?; +/// assert!(old.is_none()); +/// assert!(!xa.is_empty()); +/// +/// match xa.load(0) { +/// Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0xdead), +/// _ =3D> panic!("expected Int"), +/// } +/// +/// let old =3D xa.store(0, Entry::int::<0xcafe>(), flags::GFP_KERNEL)?; +/// match old { +/// Some(Entry::Int(v)) =3D> assert_eq!(v, 0xdead), +/// _ =3D> panic!("expected old Int"), +/// } +/// +/// match xa.erase(0) { +/// Some(Entry::Int(v)) =3D> assert_eq!(v, 0xcafe), +/// _ =3D> panic!("expected erased Int"), +/// } +/// assert!(xa.erase(1).is_some()); +/// assert!(xa.is_empty()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// # Invariants +/// +/// - `T::FOREIGN_ALIGN >=3D 4`, ensuring pointer entries do not collide w= ith the integer or internal +/// entry encoding. +/// - `SHIFT > 0` and `SIZE =3D=3D 1 << SHIFT`. +/// - Every slot in every node satisfies the `Slot` invariants. +/// - Interior levels (level > 0) contain only empty or node slots. Leaf l= evel (level 0) contains +/// only empty, `Int`, or `Pointer` slots. +/// - The subtree below every node slot contains at least one of the `Entr= y` types (`Int` or +/// `Pointer`). +pub struct XArray { + root: Node, +} + +impl Default for= XArray { + fn default() -> Self { + Self::new() + } +} + +impl XArray { + const fn validate() { + const_assert!(SHIFT > 0, "SHIFT must be > 0"); + const_assert!(SIZE =3D=3D (1 << SHIFT), "SIZE !=3D 1 << SHIFT"); + const_assert!( + T::FOREIGN_ALIGN >=3D 4, + "ForeignOwnable pointers must be 4-byte aligned" + ); + } + + /// Creates a new empty [`XArray`]. + pub const fn new() -> Self { + Self::validate(); + // INVARIANT: + // - `Self::validate` checks `T::FOREIGN_ALIGN >=3D 4`, `SHIFT > 0= ` and `SIZE =3D=3D 1 << SHIFT` + // at compile time. + // - `Node::new` fills every slot with `Slot::EMPTY`, which satisf= ies the empty-slot case + // of the `Slot` invariants. + // - Every slot is empty, and an empty slot is valid at any level. + XArray { root: Node::new() } + } + + /// Returns the number of levels in the tree. + const fn levels() -> usize { + (usize::BITS as usize).div_ceil(SHIFT) + } + + /// Returns `true` if the tree contains no entries. + /// + /// Scanning the root node suffices: by the type invariants, every nod= e slot in it leads to at + /// least one entry. + pub fn is_empty(&self) -> bool { + self.root.is_empty() + } + + /// Erases the entry at `index`. + /// + /// Returns the previous entry, or [`None`] if the slot was empty. Emp= ty intermediate nodes are + /// freed during traversal. + pub fn erase(&mut self, index: usize) -> Option> { + self.root.erase(index, Self::levels() - 1) + } + + /// Stores an entry at `index`. + /// + /// Returns the previous entry, or [`None`] if the slot was empty. + /// + /// # Errors + /// + /// Returns a [`StoreError`] carrying the entry back to the caller, wi= th error [`ENOMEM`] if + /// a new intermediate node cannot be allocated. A failed stored leave= s the tree unchanged. For + /// C callers, [`EINVAL`] in case of tree corruption detection. + pub fn store( + &mut self, + index: usize, + entry: Entry, + flags: Flags, + ) -> Result>, StoreError> { + self.root.store(index, entry, Self::levels() - 1, flags) + } + + /// Loads the entry at `index`. + /// + /// Returns [`None`] if the slot is empty. The returned [`BorrowedEntr= y`] is a value that + /// borrows from the array where pointer entries carry `T::Borrowed<'_= >` (e.g., `&T` for + /// `KBox`), and integer entries carry a copy of the [`Value`]. + pub fn load(&self, index: usize) -> Option> { + self.root.load(index, Self::levels() - 1) + } + + /// Loads the entry at `index` for mutation. + /// + /// Returns [`None`] if the slot is empty. The returned [`BorrowedEntr= yMut`] is a value that + /// borrows from the array where pointer entries carry `T::BorrowedMut= <'_>` (e.g., `&mut T` for + /// `KBox`), and integer entries carry a copy of the [`Value`]. + pub fn load_mut(&mut self, index: usize) -> Option> { + self.root.load_mut(index, Self::levels() - 1) + } +} + +/// The internal storage unit: a single `usize` encoding an [`Entry`] or a= n internal node pointer. +/// +/// # Invariants +/// +/// The encoded value `self.0` is one of: +/// - `0`: the slot is empty. +/// - An odd value `(v << 1) | 1`: an integer value `v` where `v <=3D usiz= e::MAX >> 1`. +/// - An even, non-zero value with bits `1:0 =3D=3D 0b00`: a valid, non-nu= ll pointer previously returned +/// by [`ForeignOwnable::into_foreign()`]. +/// - An even, non-zero value with bits `1:0 =3D=3D 0b10` and value > `NOD= E_THRESHOLD`: a valid pointer +/// to a live `Node` allocation, created by [`Slot::mk_n= ode()`] from +/// [`KBox::into_raw()`] tagged with `| 2`. The slot owns the [`KBox`] allocation. +// +// All entries with bits `1:0 =3D=3D 0b10` are internal to the XArray impl= ementation. The encoded value +// distinguishes sub-types: +// +// - Offset 0..=3D62, encoded 2..=3D250: sibling entries. +// The encoded value contains the offset of the canonical slot within th= e same node (multi-index +// entries, CONFIG_XARRAY_MULTI). +// +// - Logical 256, encoded 1026: retry (XA_RETRY_ENTRY). +// Tombstone signaling concurrent tree modification; RCU lock-free reade= rs must restart. +// +// - Logical 257, encoded 1030: zero (XA_ZERO_ENTRY). +// Placeholder marking a slot as occupied but logically empty (xa_reserv= e, XA_FLAGS_TRACK_FREE). +// +// - Encoded value > `NODE_THRESHOLD` (4096): node pointers (heap addresse= s tagged with | 2). Always +// above this threshold. +// +// Note: C error entries (xa_is_err()) also encode as internal entries wit= h values far above this +// threshold. They are never stored in tree slots, only returned by the XA= rray state machine API. C +// callers bypass this assumption; the FFI layer must reject error entries= before they reach Rust, +// where kind() would misclassify them as Node, causing as_node() to deref= erence an invalid +// pointer. +// +// This implementation only creates node pointers via `mk_node()`. The oth= er sub-types are reserved +// for future RCU and multi-index support. See include/linux/xarray.h. +#[repr(transparent)] +struct Slot(usiz= e, PhantomData); + +impl Default for= Slot { + fn default() -> Self { + Self::EMPTY + } +} + +#[derive(Copy, Clone)] +enum SlotType { + Empty, + Pointer, + Internal, + Node, // Internal with value > NODE_THRESHOLD. + Int, +} + +impl Slot { + // INVARIANT: `0` is the encoding for an empty slot. + const EMPTY: Self =3D Slot(0, PhantomData); + + /// Encodes an [`Entry`] into a [`Slot`] for tree storage. + fn encode(entry: Entry) -> Self { + const_assert!( + T::FOREIGN_ALIGN >=3D 4, + "ForeignOwnable pointers must be 4-byte aligned" + ); + + match entry { + Entry::Int(v) =3D> { + // INVARIANT: `*v <=3D usize::MAX >> 1` is guaranteed by `= Value` (`Bounded`), so the + // shift cannot overflow and the encoded value is odd. + Slot((*v << 1) | 1, PhantomData) + } + Entry::Pointer(p) =3D> { + let bits =3D p.into_foreign() as usize; + debug_assert!(bits !=3D 0, "ForeignOwnable returned null"); + debug_assert!(bits & 3 =3D=3D 0, "ForeignOwnable pointer n= ot 4-byte aligned"); + // INVARIANT: `into_foreign()` guarantees a non-null point= er aligned to + // `T::FOREIGN_ALIGN`, and `const_assert!(T::FOREIGN_ALIGN= >=3D 4)` above ensures + // bits `1:0 =3D=3D 0b00`. + Slot(bits, PhantomData) + } + } + } + + /// Decodes a [`Slot`] into an owned [`Entry`], consuming the slot. + /// + /// Returns [`None`] for empty slots. + fn decode(self) -> Option> { + let slot_type =3D self.kind(); + let bits =3D mem::ManuallyDrop::new(self).0; + + match slot_type { + SlotType::Empty =3D> None, + // Undo the `(v << 1) | 1` encoding from `Slot::encode`. + SlotType::Int =3D> Some(Entry::Int(Value::from_expr(bits >> 1)= )), + SlotType::Node | SlotType::Internal =3D> { + debug_assert!(false, "attempt to decode internal/node entr= y"); + None + } + SlotType::Pointer =3D> { + // SAFETY: + // - By the type invariant, a slot classified `Pointer` ho= lds a pointer returned by + // a previous call to `T::into_foreign()`. + // - `decode` takes the slot by value, so the caller has a= lready removed it from + // the tree, and `ManuallyDrop` suppresses `Slot::drop`.= This is therefore the + // only `from_foreign` call for this pointer. + Some(Entry::Pointer(unsafe { + T::from_foreign(bits as *mut c_void) + })) + } + } + } + + /// Borrows the entry in this slot without consuming it. + /// + /// Returns [`None`] for empty slots. Pointer entries are borrowed via + /// [`ForeignOwnable::borrow()`]. + fn borrow(&self) -> Option> { + let slot_type =3D self.kind(); + let bits =3D self.0; + + match slot_type { + SlotType::Empty =3D> None, + // Undo the `(v << 1) | 1` encoding from `Slot::encode`. + SlotType::Int =3D> Some(BorrowedEntry::Int(Value::from_expr(bi= ts >> 1))), + SlotType::Node | SlotType::Internal =3D> { + debug_assert!(false, "attempt to borrow internal/node entr= y"); + None + } + SlotType::Pointer =3D> { + // SAFETY: + // - By the type invariant, a slot classified `Pointer` ho= lds a pointer returned by + // a previous call to `T::into_foreign()`. + // - Every path that reaches `from_foreign` for this slot = needs ownership of it + // (`decode`) or a unique borrow (`Slot::drop`), and rea= ching either from the + // array requires `&mut self` on the `XArray`. Neither c= an coexist with this + // shared borrow, so any `from_foreign` on this pointer = happens after the borrow + // ends. + Some(BorrowedEntry::Pointer(unsafe { + T::borrow(bits as *mut c_void) + })) + } + } + } + + /// Mutably borrows the entry in this slot without consuming it. + /// + /// Returns [`None`] for empty slots. Pointer entries are borrowed via + /// [`ForeignOwnable::borrow_mut()`]; integer entries are returned by = value. + fn borrow_mut(&mut self) -> Option> { + let slot_type =3D self.kind(); + let bits =3D self.0; + + match slot_type { + SlotType::Empty =3D> None, + // Undo the `(v << 1) | 1` encoding from `Slot::encode`. + SlotType::Int =3D> Some(BorrowedEntryMut::Int(Value::from_expr= (bits >> 1))), + SlotType::Node | SlotType::Internal =3D> { + debug_assert!(false, "attempt to borrow internal/node entr= y"); + None + } + SlotType::Pointer =3D> { + // SAFETY: + // - By the type invariant, a slot classified `Pointer` ho= lds a pointer returned by + // a previous call to `T::into_foreign()`. + // - The returned value borrows `self` mutably, so no othe= r `borrow()` or + // `borrow_mut()` on this slot can overlap it, and every= path that reaches + // `from_foreign` for this slot (`decode`, `Slot::drop`)= needs the slot by value + // or by unique borrow, so any `from_foreign` on this po= inter happens after the + // borrow ends. + Some(BorrowedEntryMut::Pointer(unsafe { + T::borrow_mut(bits as *mut c_void) + })) + } + } + } + + // The boundary between internal entries and node pointers. + const NODE_THRESHOLD: usize =3D 4096; + + #[inline] + fn kind(&self) -> SlotType { + let slot =3D self.0; + if slot =3D=3D 0 { + return SlotType::Empty; + } + match slot & 3 { + 2 if slot > Self::NODE_THRESHOLD =3D> SlotType::Node, + 2 =3D> SlotType::Internal, + 1 | 3 =3D> SlotType::Int, + _ =3D> SlotType::Pointer, + } + } + + #[inline] + fn is_empty(&self) -> bool { + matches!(self.kind(), SlotType::Empty) + } + + #[inline] + fn is_node(&self) -> bool { + matches!(self.kind(), SlotType::Node) + } + + /// Returns a shared reference to the child node pointed to by this en= try, or [`None`] if this + /// is not a node slot. + fn as_node(&self) -> Option<&Node> { + if !self.is_node() { + return None; + } + let ptr =3D (self.0 & !3) as *const Node; + // SAFETY: + // - By the type invariant, a slot classified `Node` holds `KBox::= into_raw()` of a valid, + // live `KBox>` allocation owned by this sl= ot. `& !3` reverses the + // `| 2` tag. + // - The returned reference borrows `self`, so the slot cannot be = modified and the + // allocation cannot be freed while it is live. + Some(unsafe { &*ptr }) + } + + /// Returns a mutable reference to the child node pointed to by this e= ntry, or [`None`] if this + /// is not a node slot. + fn as_node_mut(&mut self) -> Option<&mut Node> { + if !self.is_node() { + return None; + } + let ptr =3D (self.0 & !3) as *mut Node; + // SAFETY: + // - By the type invariant, a slot classified `Node` holds `KBox::= into_raw()` of a valid, + // live `KBox>` allocation owned by this sl= ot. `& !3` reverses the + // `| 2` tag. + // - The returned reference borrows `self` mutably, so no other re= ference to the allocation + // can exist and the slot cannot be modified while it is live. + Some(unsafe { &mut *ptr }) + } + + /// Creates a node slot from a heap-allocated [`Node`]. + fn mk_node(node: KBox>) -> Self { + let ptr =3D KBox::into_raw(node) as usize; + debug_assert!(ptr & 3 =3D=3D 0, "Node pointer not aligned"); + // INVARIANT: `ptr` owns a live `KBox` allocation from `into= _raw()`, so it is at least + // 4-byte aligned (checked above) and `| 2` gives bits `1:0 =3D=3D= 0b10`. Kernel heap addresses + // are far above `NODE_THRESHOLD`, so the result classifies as nod= e. + Slot(ptr | 2, PhantomData) + } +} + +impl Drop for Sl= ot { + fn drop(&mut self) { + match self.kind() { + SlotType::Pointer =3D> { + // SAFETY: + // - By the type invariant, a slot classified `Pointer` ho= lds a pointer returned by + // a previous call to `T::into_foreign()`. + // - Every other `from_foreign` path (`decode`) consumes t= he slot through + // `ManuallyDrop`, which suppresses this destructor, so = this is the only + // `from_foreign` call for this pointer. + drop(unsafe { T::from_foreign(self.0 as *mut c_void) }); + } + SlotType::Node =3D> { + let ptr =3D (self.0 & !3) as *mut Node; + // SAFETY: + // - By the type invariant, a slot classified `Node` holds= a pointer produced by + // `KBox::into_raw()` in `Slot::mk_node()`, tagged with = `| 2`; `& !3` above + // reverses the tag. + // - The slot is being dropped and passes that ownership t= o the reconstructed box. + // `decode()`, the only other consumer of a slot by valu= e, never accepts node + // slots, so this is the only `KBox::from_raw()` for thi= s pointer. + // + // Dropping the box drops the child's slots in turn, freei= ng the subtree. The + // recursion is bounded by the tree depth. + drop(unsafe { KBox::from_raw(ptr) }); + } + SlotType::Internal =3D> { + debug_assert!(false, "internal entry must not reach Slot::= drop"); + } + _ =3D> {} + } + } +} + +/// A single node in the radix tree. Each node contains `SIZE` slots, wher= e each slot may be empty, +/// contain a user entry (integer or pointer), or point to a child node at= the next tree level. +/// +/// # Invariants +/// +/// - Interior nodes (level > 0): each slot is either `Empty` or a `Node` = pointer created by +/// [`Slot::mk_node()`] from a valid [`KBox>`] allo= cation. +/// - Leaf nodes (level =3D=3D 0): each slot is either `Empty`, `Int`, or = `Pointer`. No `Node` or +/// `Internal` slots may appear at level 0. +struct Node { + slots: [Slot; SIZE], +} + +impl Node { + // Bitmask for extracting the slot offset. Equivalent to XA_CHUNK_MASK. + const MASK: usize =3D SIZE - 1; + + const fn new() -> Self { + // INVARIANT: every slot is `Slot::EMPTY`, so the node satisfies t= he type invariants at any + // level. + Self { + slots: [const { Slot::EMPTY }; SIZE], + } + } + + /// Extracts the slot index for `index` at the given tree `level`. + /// + /// Equivalent to `get_offset()` (see `lib/xarray.c`). + #[inline] + fn slot_index(index: usize, level: usize) -> usize { + (index >> (level * SHIFT)) & Self::MASK + } + + /// Returns `true` if every slot in this node is empty. + fn is_empty(&self) -> bool { + self.slots.iter().all(|slot| slot.is_empty()) + } + + /// Erases the entry at `index`. + /// + /// Returns the previous entry, or [`None`] if the slot was empty. Fre= es empty intermediate + /// nodes on the way back up. + fn erase(&mut self, index: usize, level: usize) -> Option> { + let slot_index =3D Self::slot_index(index, level); + let slot =3D &mut self.slots[slot_index]; + if level =3D=3D 0 { + debug_assert!(!slot.is_node(), "Found node pointer at leaf lev= el"); + // INVARIANT: `mem::take` leaves `Slot::EMPTY` behind, which i= s permitted at leaf level. + let old =3D mem::take(slot); + return old.decode(); + } + + if let Some(child) =3D slot.as_node_mut() { + let old_value =3D child.erase(index, level - 1); + if child.is_empty() { + // INVARIANT: `mem::take` leaves `Slot::EMPTY` behind, whi= ch is permitted at + // interior level. Dropping the taken slot frees the child= node. + drop(mem::take(slot)); + } + old_value + } else { + // Values at intermediate levels indicate tree corruption. + debug_assert!(slot.is_empty(), "Non-null non-node entry"); + None + } + } + + /// Builds an unlinked subtree that holds `entry` at `index`, from `le= vel` down to leaf. + /// + /// A failed node allocation at any level returns the [`StoreError`] c= arrying `entry`, and the + /// nodes built so far are dropped automatically on the way out. The c= aller links the subtree + /// into the main tree only after the whole build has succeeded. + fn mk_subtree( + index: usize, + entry: Entry, + level: usize, + flags: Flags, + ) -> Result, StoreError> { + let mut node =3D match KBox::new(Self::new(), flags) { + Ok(node) =3D> node, + Err(error) =3D> { + return Err(StoreError { + error: error.into(), + entry, + }) + } + }; + let slot_index =3D Self::slot_index(index, level); + if level =3D=3D 0 { + // INVARIANT: `Slot::encode` returns an `Int` or `Pointer` slo= t, both of which are + // permitted at leaf level. + node.slots[slot_index] =3D Slot::encode(entry); + } else { + let child_node =3D Self::mk_subtree(index, entry, level - 1, f= lags)?; + // INVARIANT: `Slot::mk_node` returns a node slot holding a va= lid `KBox`, which + // is permitted at interior level. The child subtree holds `en= try` at its leaf level. + node.slots[slot_index] =3D Slot::mk_node(child_node); + } + Ok(node) + } + + /// Stores `entry` at `index`, allocating intermediate nodes as needed. + /// + /// Returns the previous entry, or [`None`] if the slot was empty. + fn store( + &mut self, + index: usize, + entry: Entry, + level: usize, + flags: Flags, + ) -> Result>, StoreError> { + let slot_index =3D Self::slot_index(index, level); + let slot =3D &mut self.slots[slot_index]; + if level =3D=3D 0 { + debug_assert!(!slot.is_node(), "Found node pointer at leaf lev= el"); + // INVARIANT: `Slot::encode` returns an `Int` or `Pointer` slo= t, both of which are + // permitted at leaf level. + let old =3D mem::replace(slot, Slot::encode(entry)); + return Ok(old.decode()); + } + + if slot.is_empty() { + // Link the subtree only after every allocation has succeeded.= A failed allocation drops + // the partial subtree and leaves the main tree untouched. + let child_node =3D Self::mk_subtree(index, entry, level - 1, f= lags)?; + // INVARIANT: `Slot::mk_node` returns a node slot holding a va= lid `KBox`, which + // is permitted at interior level. The subtree holds `entry` a= t its leaf level. + *slot =3D Slot::mk_node(child_node); + return Ok(None); + } + + let Some(child_node) =3D slot.as_node_mut() else { + // Unreachable unless the tree is corrupt. Rust type safety pr= events this; C callers + // bypass that guarantee, so the FFI layer must ensure tree in= tegrity before reaching + // this path. + debug_assert!(false, "Non-null non-node entry"); + return Err(StoreError { + error: EINVAL, + entry, + }); + }; + // Any code after this call would block tail-call elimination. + child_node.store(index, entry, level - 1, flags) + } + + /// Loads the entry at `index`. + /// + /// Returns a borrowed view of the entry, or [`None`] if the slot is e= mpty. + fn load(&self, index: usize, level: usize) -> Option> { + let slot_index =3D Self::slot_index(index, level); + let slot =3D &self.slots[slot_index]; + if level =3D=3D 0 { + debug_assert!(!slot.is_node(), "Found node pointer at leaf lev= el"); + return slot.borrow(); + } + + // Values at intermediate levels indicate tree corruption: trap wh= en debug assertions are + // enabled, load as absent otherwise. Same shape as `load_mut()`, = where the borrow checker + // constraints it. + debug_assert!(slot.is_node() || slot.is_empty(), "Non-null non-nod= e entry"); + slot.as_node()?.load(index, level - 1) + } + + /// Loads the entry at `index` for mutation. + /// + /// Returns [`None`] if the slot is empty. + fn load_mut(&mut self, index: usize, level: usize) -> Option> { + let slot_index =3D Self::slot_index(index, level); + let slot =3D &mut self.slots[slot_index]; + if level =3D=3D 0 { + debug_assert!(!slot.is_node(), "Found node pointer at leaf lev= el"); + return slot.borrow_mut(); + } + + // Values at intermediate levels indicate tree corruption: trap wh= en debug assertions are + // enabled, load as absent otherwise. + debug_assert!(slot.is_node() || slot.is_empty(), "Non-null non-nod= e entry"); + slot.as_node_mut()?.load_mut(index, level - 1) + } +} + +#[macros::kunit_tests(rust_rxarray)] +mod tests { + use super::*; + use kernel::alloc::flags; + + // Dispatches a test across all SHIFT/SIZE configurations. Default arm= passes + // with T =3D KBox; `ptr` arm passes only for point= er tests that must construct + // KBox values because ForeignOwnable has no constructor, so T mu= st be concrete. + macro_rules! for_each_xarray { + ($fn:ident) =3D> { + $fn::, 4, 16>(); + $fn::, 6, 64>(); + }; + (ptr, $fn:ident) =3D> { + $fn::<4, 16>(); + $fn::<6, 64>(); + }; + } + + // `XArray` carries no explicit `Send`/`Sync` impl: the `PhantomData` in `Slot` makes the + // auto-derived bounds follow `T`. These assertions fail to compile if= that ever stops holding. + const fn assert_send() {} + const fn assert_sync() {} + + fn assert_auto_traits_impl< + T: ForeignOwnable + Send + Sync, + const SHIFT: usize, + const SIZE: usize, + >() { + assert_send::>(); + assert_sync::>(); + } + + #[test] + fn assert_auto_traits() { + for_each_xarray!(assert_auto_traits_impl); + } + + fn new_is_empty_impl() { + let xa =3D XArray::::new(); + assert!(xa.is_empty()); + assert!(xa.load(0).is_none()); + assert!(xa.load(usize::MAX).is_none()); + } + + #[test] + fn new_is_empty() { + for_each_xarray!(new_is_empty_impl); + } + + fn store_load_value_impl() { + let mut xa =3D XArray::::new(); + let old =3D xa.store(0, Entry::int::<137>(), flags::GFP_KERNEL).un= wrap(); + assert!(old.is_none()); + assert!(!xa.is_empty()); + + match xa.load(0) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 137), + _ =3D> panic!("expected Int"), + }; + } + + #[test] + fn store_load_value() { + for_each_xarray!(store_load_value_impl); + } + + fn overwrite_value_impl() { + let mut xa =3D XArray::::new(); + xa.store(137, Entry::int::<1001>(), flags::GFP_KERNEL) + .unwrap(); + let old =3D xa + .store(137, Entry::int::<2002>(), flags::GFP_KERNEL) + .unwrap(); + + match old { + Some(Entry::Int(v)) =3D> assert_eq!(v, 1001), + _ =3D> panic!("expected old Int"), + } + match xa.load(137) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 2002), + _ =3D> panic!("expected Int"), + }; + } + + #[test] + fn overwrite_value() { + for_each_xarray!(overwrite_value_impl); + } + + fn erase_value_impl() { + let mut xa =3D XArray::::new(); + xa.store(137, Entry::int::<1001>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(138, Entry::int::<1002>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(139, Entry::int::<1003>(), flags::GFP_KERNEL) + .unwrap(); + + let old =3D xa.erase(138); + match old { + Some(Entry::Int(v)) =3D> assert_eq!(v, 1002), + _ =3D> panic!("expected erased Int"), + } + assert!(xa.load(138).is_none()); + + match xa.load(137) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 1001), + _ =3D> panic!("expected Int at neighbor"), + } + match xa.load(139) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 1003), + _ =3D> panic!("expected Int at neighbor"), + }; + } + + #[test] + fn erase_value() { + for_each_xarray!(erase_value_impl); + } + + // Two paths: (1) empty tree with no nodes allocated, (2) intermediate= nodes exist but the + // target leaf slot was never stored. + fn erase_nonexistent_impl() { + let mut xa =3D XArray::::new(); + assert!(xa.erase(999).is_none()); + + // Intermediate nodes exist for index 0; index 1 shares the same l= eaf node but its slot was + // never populated. + xa.store(0, Entry::int::<1>(), flags::GFP_KERNEL).unwrap(); + assert!(xa.erase(1).is_none()); + match xa.load(0) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 1), + _ =3D> panic!("expected Int after erasing neighbor"), + }; + } + + #[test] + fn erase_nonexistent() { + for_each_xarray!(erase_nonexistent_impl); + } + + // After erase frees intermediate nodes, re-store at the same index mu= st re-allocate them. + fn erase_and_restore_impl() { + let mut xa =3D XArray::::new(); + xa.store(137, Entry::int::<1001>(), flags::GFP_KERNEL) + .unwrap(); + + let erased =3D xa.erase(137); + match erased { + Some(Entry::Int(v)) =3D> assert_eq!(v, 1001), + _ =3D> panic!("expected erased Int"), + } + assert!(xa.load(137).is_none()); + + let old =3D xa + .store(137, Entry::int::<2002>(), flags::GFP_KERNEL) + .unwrap(); + assert!(old.is_none()); + match xa.load(137) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 2002), + _ =3D> panic!("expected Int"), + }; + } + + #[test] + fn erase_and_restore() { + for_each_xarray!(erase_and_restore_impl); + } + + // Stores at node boundaries to exercise tree structure: + // - SIZE-1: last slot in the first leaf node. + // - SIZE: first index requiring a second leaf node. + // - SIZE*SIZE-1: last index in the first level-1 subtree. + // - SIZE*SIZE: first index requiring a third tree level. + fn store_at_boundaries_impl() { + let mut xa =3D XArray::::new(); + xa.store(SIZE - 1, Entry::int::<0xA>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(SIZE, Entry::int::<0xB>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(SIZE * SIZE - 1, Entry::int::<0xC>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(SIZE * SIZE, Entry::int::<0xD>(), flags::GFP_KERNEL) + .unwrap(); + + match xa.load(SIZE - 1) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0xA), + _ =3D> panic!("expected Int at SIZE-1"), + } + match xa.load(SIZE) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0xB), + _ =3D> panic!("expected Int at SIZE"), + } + match xa.load(SIZE * SIZE - 1) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0xC), + _ =3D> panic!("expected Int at SIZE*SIZE-1"), + } + match xa.load(SIZE * SIZE) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0xD), + _ =3D> panic!("expected Int at SIZE*SIZE"), + } + assert!(xa.load(0).is_none()); + } + + #[test] + fn store_at_boundaries() { + for_each_xarray!(store_at_boundaries_impl); + } + + // For XArray6 this allocates 10 intermediate nodes; for XArray4, 15. = Erasing verifies cascading + // cleanup frees all intermediate nodes back to the root. + fn store_at_max_index_impl() { + let mut xa =3D XArray::::new(); + xa.store(usize::MAX, Entry::int::<0xFF>(), flags::GFP_KERNEL) + .unwrap(); + match xa.load(usize::MAX) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0xFF), + _ =3D> panic!("expected Int at usize::MAX"), + } + assert!(xa.load(0).is_none()); + + match xa.erase(usize::MAX) { + Some(Entry::Int(v)) =3D> assert_eq!(v, 0xFF), + _ =3D> panic!("expected erased Int at usize::MAX"), + } + assert!(xa.load(usize::MAX).is_none()); + assert!(xa.is_empty()); + } + + #[test] + fn store_at_max_index() { + for_each_xarray!(store_at_max_index_impl); + } + + // SIZE*3 entries spanning multiple leaf nodes. Erases even indices an= d verifies odd indices + // remain intact. Erase return values are not checked here; that path = is covered by erase_value. + fn bulk_operations_impl() { + let mut xa =3D XArray::::new(); + let count =3D SIZE * 3; + + for i in 0..count { + xa.store(i, Entry::try_int(i * 10).unwrap(), flags::GFP_KERNEL) + .unwrap(); + } + + for i in 0..count { + if i % 2 =3D=3D 0 { + xa.erase(i); + } + } + + for i in 0..count { + match xa.load(i) { + Some(BorrowedEntry::Int(v)) =3D> { + assert_eq!(i % 2, 1); + assert_eq!(v, i * 10); + } + Some(BorrowedEntry::Pointer(_)) =3D> { + panic!("unexpected Pointer in value-only tree") + } + None =3D> assert_eq!(i % 2, 0), + } + } + } + + #[test] + fn bulk_operations() { + for_each_xarray!(bulk_operations_impl); + } + + // Stores entries in different subtrees (indices 0 and SIZE diverge at= level 1), then erases + // both. The second erase cascades cleanup through intermediate nodes = that no longer have any + // children. + fn erase_all_restores_empty_impl() { + let mut xa =3D XArray::::new(); + xa.store(0, Entry::int::<1>(), flags::GFP_KERNEL).unwrap(); + xa.store(SIZE, Entry::int::<2>(), flags::GFP_KERNEL) + .unwrap(); + assert!(!xa.is_empty()); + + xa.erase(0); + assert!(!xa.is_empty()); + xa.erase(SIZE); + assert!(xa.is_empty()); + } + + #[test] + fn erase_all_restores_empty() { + for_each_xarray!(erase_all_restores_empty_impl); + } + + // Entry::int::<0>() encodes as (0 << 1) | 1 =3D 1; must not be confus= ed with the empty slot + // encoding (0). + fn value_zero_impl() { + let mut xa =3D XArray::::new(); + xa.store(0, Entry::int::<0>(), flags::GFP_KERNEL).unwrap(); + assert!(!xa.is_empty()); + match xa.load(0) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 0), + _ =3D> panic!("expected Int"), + } + + match xa.erase(0) { + Some(Entry::Int(v)) =3D> assert_eq!(v, 0), + _ =3D> panic!("expected erased Int"), + } + assert!(xa.load(0).is_none()); + } + + #[test] + fn value_zero() { + for_each_xarray!(value_zero_impl); + } + + // Pointer-specific tests (ForeignOwnable path with KBox). + + fn store_load_pointer_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let boxed =3D KBox::new(42u64, flags::GFP_KERNEL).unwrap(); + let old =3D xa + .store(0, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + assert!(old.is_none()); + + match xa.load(0) { + Some(BorrowedEntry::Pointer(val)) =3D> assert_eq!(*val, 42u64), + _ =3D> panic!("expected Pointer"), + } + } + + #[test] + fn store_load_pointer() { + for_each_xarray!(ptr, store_load_pointer_impl); + } + + // Erase returns the owned KBox, verifying that Slot::decode transfers= ownership via + // ManuallyDrop without double-free or leak. + fn erase_returns_pointer_impl()= { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let boxed =3D KBox::new(99u64, flags::GFP_KERNEL).unwrap(); + xa.store(5, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + + match xa.erase(5) { + Some(Entry::Pointer(owned)) =3D> assert_eq!(*owned, 99u64), + _ =3D> panic!("expected owned Pointer"), + } + assert!(xa.load(5).is_none()); + } + + #[test] + fn erase_returns_pointer() { + for_each_xarray!(ptr, erase_returns_pointer_impl); + } + + fn overwrite_pointer_with_value_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let boxed =3D KBox::new(42u64, flags::GFP_KERNEL).unwrap(); + xa.store(0, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + + let old =3D xa.store(0, Entry::int::<137>(), flags::GFP_KERNEL).un= wrap(); + match old { + Some(Entry::Pointer(p)) =3D> assert_eq!(*p, 42u64), + _ =3D> panic!("expected old Pointer"), + } + match xa.load(0) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 137), + _ =3D> panic!("expected Int"), + } + } + + #[test] + fn overwrite_pointer_with_value() { + for_each_xarray!(ptr, overwrite_pointer_with_value_impl); + } + + fn overwrite_value_with_pointer_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + xa.store(0, Entry::int::<137>(), flags::GFP_KERNEL).unwrap(); + + let boxed =3D KBox::new(42u64, flags::GFP_KERNEL).unwrap(); + let old =3D xa + .store(0, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + match old { + Some(Entry::Int(v)) =3D> assert_eq!(v, 137), + _ =3D> panic!("expected old Int"), + } + match xa.load(0) { + Some(BorrowedEntry::Pointer(val)) =3D> assert_eq!(*val, 42u64), + _ =3D> panic!("expected Pointer"), + } + } + + #[test] + fn overwrite_value_with_pointer() { + for_each_xarray!(ptr, overwrite_value_with_pointer_impl); + } + + fn mixed_values_and_pointers_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let boxed =3D KBox::new(42u64, flags::GFP_KERNEL).unwrap(); + xa.store(0, Entry::int::<100>(), flags::GFP_KERNEL).unwrap(); + xa.store(1, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + + match xa.load(0) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, 100), + _ =3D> panic!("expected Int"), + } + match xa.load(1) { + Some(BorrowedEntry::Pointer(val)) =3D> assert_eq!(*val, 42u64), + _ =3D> panic!("expected Pointer"), + } + } + + #[test] + fn mixed_values_and_pointers() { + for_each_xarray!(ptr, mixed_values_and_pointers_impl); + } + + // Drops a tree with mixed Int (even indices) and Pointer (odd indices= ) entries. Correctness + // depends on KASAN/kmemleak detecting leaks or double-frees. + fn drop_frees_pointers_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let count =3D SIZE * 2; + for i in 0..count { + if i % 2 =3D=3D 0 { + xa.store(i, Entry::try_int(i * 10).unwrap(), flags::GFP_KE= RNEL) + .unwrap(); + } else { + let b =3D KBox::new(i as u64, flags::GFP_KERNEL).unwrap(); + xa.store(i, Entry::Pointer(b), flags::GFP_KERNEL).unwrap(); + } + } + } + + #[test] + fn drop_frees_pointers() { + for_each_xarray!(ptr, drop_frees_pointers_impl); + } + + // usize::MAX >> 1 is the maximum valid integer entry. Exercises both = compile-time validation + // (Entry::int) and runtime validation (Entry::try_int). + fn value_encoding_boundary_impl() { + let mut xa =3D XArray::::new(); + let max =3D usize::MAX >> 1; + + // Runtime: try_int accepts max, rejects max+1. + assert!(Entry::::try_int(max).is_some()); + assert!(Entry::::try_int(max + 1).is_none()); + assert!(Entry::::try_int(usize::MAX).is_none()); + + // Compile-time: `Entry::int` validates via `const_assert!` in `Bo= unded::new`. + xa.store(0, Entry::int::<{ usize::MAX >> 1 }>(), flags::GFP_KERNEL) + .unwrap(); + match xa.load(0) { + Some(BorrowedEntry::Int(v)) =3D> assert_eq!(v, max), + _ =3D> panic!("expected max value"), + }; + } + + #[test] + fn value_encoding_boundary() { + for_each_xarray!(value_encoding_boundary_impl); + } + + fn overwrite_pointer_with_pointer_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let first =3D KBox::new(42u64, flags::GFP_KERNEL).unwrap(); + xa.store(0, Entry::Pointer(first), flags::GFP_KERNEL) + .unwrap(); + + let second =3D KBox::new(99u64, flags::GFP_KERNEL).unwrap(); + let old =3D xa + .store(0, Entry::Pointer(second), flags::GFP_KERNEL) + .unwrap(); + match old { + Some(Entry::Pointer(p)) =3D> assert_eq!(*p, 42u64), + _ =3D> panic!("expected old Pointer"), + } + match xa.load(0) { + Some(BorrowedEntry::Pointer(val)) =3D> assert_eq!(*val, 99u64), + _ =3D> panic!("expected new Pointer"), + } + } + + #[test] + fn overwrite_pointer_with_pointer() { + for_each_xarray!(ptr, overwrite_pointer_with_pointer_impl); + } + + fn erase_at_boundaries_impl() { + let mut xa =3D XArray::::new(); + xa.store(SIZE - 1, Entry::int::<0xA>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(SIZE, Entry::int::<0xB>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(SIZE * SIZE - 1, Entry::int::<0xC>(), flags::GFP_KERNEL) + .unwrap(); + xa.store(SIZE * SIZE, Entry::int::<0xD>(), flags::GFP_KERNEL) + .unwrap(); + + match xa.erase(SIZE * SIZE) { + Some(Entry::Int(v)) =3D> assert_eq!(v, 0xD), + _ =3D> panic!("expected erased Int at SIZE*SIZE"), + } + match xa.erase(SIZE * SIZE - 1) { + Some(Entry::Int(v)) =3D> assert_eq!(v, 0xC), + _ =3D> panic!("expected erased Int at SIZE*SIZE-1"), + } + match xa.erase(SIZE) { + Some(Entry::Int(v)) =3D> assert_eq!(v, 0xB), + _ =3D> panic!("expected erased Int at SIZE"), + } + match xa.erase(SIZE - 1) { + Some(Entry::Int(v)) =3D> assert_eq!(v, 0xA), + _ =3D> panic!("expected erased Int at SIZE-1"), + } + assert!(xa.is_empty()); + } + + #[test] + fn erase_at_boundaries() { + for_each_xarray!(erase_at_boundaries_impl); + } + + // Erasing the sole pointer must return the owned KBox and free all in= termediate nodes. + fn erase_last_pointer_cascading_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + let boxed =3D KBox::new(777u64, flags::GFP_KERNEL).unwrap(); + xa.store(0, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + + match xa.erase(0) { + Some(Entry::Pointer(p)) =3D> assert_eq!(*p, 777u64), + _ =3D> panic!("expected owned Pointer"), + } + assert!(xa.is_empty()); + } + + #[test] + fn erase_last_pointer_cascading() { + for_each_xarray!(ptr, erase_last_pointer_cascading_impl); + } + + fn load_mut_entries_impl() { + let mut xa =3D XArray::, SHIFT, SIZE>::new(); + assert!(xa.load_mut(0).is_none()); + + let boxed =3D KBox::new(137u64, flags::GFP_KERNEL).unwrap(); + xa.store(0, Entry::Pointer(boxed), flags::GFP_KERNEL) + .unwrap(); + xa.store(1, Entry::int::<137>(), flags::GFP_KERNEL).unwrap(); + + match xa.load_mut(0) { + Some(BorrowedEntryMut::Pointer(val)) =3D> *val =3D 131u64, + _ =3D> panic!("expected Pointer"), + } + match xa.load(0) { + Some(BorrowedEntry::Pointer(val)) =3D> assert_eq!(*val, 131u64= ), + _ =3D> panic!("expected Pointer"), + } + match xa.load_mut(1) { + Some(BorrowedEntryMut::Int(val)) =3D> assert_eq!(val, 137), + _ =3D> panic!("expected Int"), + } + } + + #[test] + fn load_mut_entries() { + for_each_xarray!(ptr, load_mut_entries_impl); + } + + fn store_error_impl() { + let err =3D StoreError { + error: ENOMEM, + entry: Entry::>::int::<137>(), + }; + match &err.entry { + Entry::Int(value) =3D> assert_eq!(*value, 137), + _ =3D> panic!("expected Int"), + } + let e: Error =3D err.into(); + assert_eq!(e.to_errno(), ENOMEM.to_errno()); + } + + #[test] + fn store_error() { + for_each_xarray!(ptr, store_error_impl); + } +} --=20 2.55.0 From nobody Thu Sep 24 14:25:40 2026 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-alma10-1.taild15c8.ts.net [100.103.45.18]) (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 3793C3A4F4A; Wed, 23 Sep 2026 21:00:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=100.103.45.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790197253; cv=none; b=ICmc2KFk6fsVsKJpsK5OzlZMCuiRUit+QzMUJvC1YCdsR1CTDbBxmt2cxLvl0sPr1NmaYypdicZbcoiz5TjMbS5fewtp+NFJnaP7Z9t3fBu4oPl+3cp4DJmpkR0fmXa5gU8gqdiq8q1Oeliwj4KQMTQph6H/V0KMhqrdHLvWCc8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790197253; c=relaxed/simple; bh=bfEks5Zx4yvkOjzagW19mZ6pxA3z77H+fB2XzlBKK4w=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=azz9a1qD4OrAaeaDY2qvG5SkinvruC1bBrAxbv1J7F/gXducbvdSwUlfmaH3EJrSFdZ5p9ne+Zeg0C91TYTnMvqn0aYKkk5f1q+3kFrRJJHOyU8GC/cfwklOq3QYR8uCv12cr4wHYr9RBZbQDR6dvY7gQsk2TBlX63hM2uzSl7g= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=UWhw/2ck; arc=none smtp.client-ip=100.103.45.18 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="UWhw/2ck" Received: by smtp.kernel.org (Postfix) with ESMTPSA id A0EE81F000FF; Wed, 23 Sep 2026 21:00:47 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1790197251; bh=mrpikVygoO69c+39ec1mzIBa190J1FVeDcEm0MS0bCI=; h=From:Date:Subject:References:In-Reply-To:To:Cc; b=UWhw/2ck3Wm6+80HXAhWWJkiZcr7yfFF7t8DooP1wMG7pDG9Os4wtU8qJMWGNpoPg ciV/94qDc8uIdMA2mcnCtjKOombVIsWoAPxjMODl9+iTmIsSsxXAnJh8Qy1H/RIvdn +6rdDExOa3xsQg9GlMfiosvPQTPZI7TAvbyFzQlM1AGXv2vVt6AQNW1mktKzByv3hK /R4uBgoFnX9FIykZVE7tZ8qTkOSQrYgJsyK+F4txmlmDqUlO5T4rLbpQWcBzbigLyx 14vIKlAQBFAHL7D+sJ4IcYdybYB4It/K/5lltoRKvJqPIDAKNynNj9k/WHy00v8+bF adUt3BqZ4QXjg== From: Daniel Gomez Date: Wed, 23 Sep 2026 23:00:28 +0200 Subject: [PATCH 2/3] rust: kernel: add bench 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 Message-Id: <20260923-rxarray-next-v1-2-92eedf185649@samsung.com> References: <20260923-rxarray-next-v1-0-92eedf185649@samsung.com> In-Reply-To: <20260923-rxarray-next-v1-0-92eedf185649@samsung.com> To: "Matthew Wilcox (Oracle)" , Miguel Ojeda , Boqun Feng , Gary Guo , =?utf-8?q?Bj=C3=B6rn_Roy_Baron?= , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , Danilo Krummrich , Daniel Almeida , Tamir Duberstein , Alexandre Courbot , =?utf-8?q?Onur_=C3=96zkan?= , Daniel Gomez , Andrew Morton Cc: Julia Lawall , Corinn Tiffany , "Liam R. Howlett" , Philipp Stanner , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Samsung GOST , Daniel Gomez X-Mailer: b4 0.16-dev X-Developer-Signature: v=1; a=ed25519-sha256; t=1790197237; l=6611; i=da.gomez@samsung.com; s=20240621; h=from:subject:message-id; bh=dqSFRTHpzxLRqBZjl34t8Db+pHpufW9lfFAmTUKo6Jg=; b=uCfMOkpad7qvZMWbiciZYLcSYhYLyxH6DfepJ2Jr/UcYKavQ6YXLJkdRn9nP26h9pJKJ3lwmo vQ39RGuAxjlAFyi3YCtKW3NGyXFn+GKuGXMjwQuB7zART1QhmvLMWgK X-Developer-Key: i=da.gomez@samsung.com; a=ed25519; pk=BqYk31UHkmv0WZShES6pIZcdmPPGay5LbzifAdZ2Ia4= From: Daniel Gomez Rust bench for sampled benchmarking with statistics. The XArray benchmark will be the first user. The runner is a module so other Rust benchmarks such as find_bit_benchmark_rust can share it. It can also be extended with percentiles in the future. Assisted-by: LLM Signed-off-by: Daniel Gomez --- MAINTAINERS | 1 + rust/kernel/bench.rs | 173 +++++++++++++++++++++++++++++++++++++++++++++++= ++++ rust/kernel/lib.rs | 1 + 3 files changed, 175 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index c40a254c35d3d..b8bdfe9e22226 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -29690,6 +29690,7 @@ W: https://rust-for-linux.com B: https://github.com/Rust-for-Linux/linux/issues C: https://rust-for-linux.zulipchat.com T: git git://git.kernel.org/pub/scm/linux/kernel/git/da.gomez/linux.git rx= array-next +F: rust/kernel/bench.rs F: rust/kernel/rxarray.rs =20 XBOX DVD IR REMOTE diff --git a/rust/kernel/bench.rs b/rust/kernel/bench.rs new file mode 100644 index 0000000000000..d1c85c49c7969 --- /dev/null +++ b/rust/kernel/bench.rs @@ -0,0 +1,173 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Sampled benchmarks with in-kernel statistics. +//! +//! Each sample times `iterations` of a workload. A [`Row`] prints the min= imum, median, maximum and +//! mean of the sample times in nanoseconds. The caller owns the timer and= the printing: +//! +//! ```ignore +//! let mut bench =3D Bencher::new(samples, entries)?; +//! pr_info!("{samples} samples x {entries} entries, ns per sample:\n"); +//! pr_info!("{}\n", bench::Heading); +//! pr_info!("{}\n", bench.run("store", XArray::new, store)); +//! pr_info!("total runtime {}\n", bench.runtime()); +//! ``` + +use crate::{ + fmt, + prelude::*, + time::{Delta, Instant, Monotonic}, // +}; + +/// The column headings of a table of [`Row`]s, in the same columns. +pub struct Heading; + +impl fmt::Display for Heading { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_fmt(fmt!( + "{:<18} {:>12} {:>12} {:>12} {:>12} {:>12}", + "benchmark", + "min", + "median", + "max", + "mean", + "runtime" + )) + } +} + +/// A wall time. +pub struct Runtime(pub Delta); + +impl fmt::Display for Runtime { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let ms =3D self.0.as_millis(); + let secs =3D ms / 1000; + let mins =3D secs / 60; + let hours =3D mins / 60; + let width =3D f.width().unwrap_or(0); + if hours > 0 { + let w =3D width.saturating_sub(4); + write!(f, "{hours:w$}h{:02}m", mins % 60) + } else if mins > 0 { + let w =3D width.saturating_sub(4); + write!(f, "{mins:w$}m{:02}s", secs % 60) + } else { + let w =3D width.saturating_sub(5); + write!(f, "{secs:w$}.{:03}s", ms % 1000) + } + } +} + +/// Stats across samples, in nanoseconds. +pub struct Stats { + /// The fastest sample. + pub min: i64, + /// The middle sample. + pub median: i64, + /// The slowest sample. + pub max: i64, + /// The mean of the samples, rounded down. + pub mean: i64, +} + +impl Stats { + /// Computes the statistics of the non-empty `samples`, sorting them i= n place. + pub fn new(samples: &mut [i64]) -> Self { + samples.sort_unstable(); + let len =3D samples.len(); + Self { + min: samples[0], + median: (samples[(len - 1) / 2] + samples[len / 2]) / 2, + max: samples[len - 1], + mean: samples.iter().sum::() / len as i64, + } + } +} + +/// One row of the table: the benchmark's name, its statistics and its wal= l time, in the columns +/// of [`Heading`]. +pub struct Row<'a> { + name: &'a str, + stats: Stats, + runtime: Runtime, +} + +impl fmt::Display for Row<'_> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_fmt(fmt!( + "{:<18} {:>12} {:>12} {:>12} {:>12} {:>12}", + self.name, + self.stats.min, + self.stats.median, + self.stats.max, + self.stats.mean, + self.runtime + )) + } +} + +/// Benchmark runner. +pub struct Bencher { + iterations: usize, + timings: KVVec, + runtime: Delta, +} + +impl Bencher { + /// Allocates one timing slot per sample up front, outside the timed l= oops. + /// + /// Returns `EINVAL` if `samples` or `iterations` is 0. + pub fn new(samples: usize, iterations: usize) -> Result { + if samples =3D=3D 0 || iterations =3D=3D 0 { + return Err(EINVAL); + } + Ok(Self { + iterations, + timings: KVVec::from_elem(0, samples, GFP_KERNEL)?, + runtime: Delta::ZERO, + }) + } + + /// Runs `bench` on a fresh `setup` value once per sample and returns = the table row of `name`. + /// + /// `bench` returns the [`Delta`] of the window it timed. + pub fn run<'a, A>( + &mut self, + name: &'a str, + setup: impl Fn() -> A, + bench: impl Fn(A, usize) -> Delta, + ) -> Row<'a> { + let start =3D Instant::::now(); + for ns in &mut self.timings { + *ns =3D bench(setup(), self.iterations).as_nanos(); + } + let elapsed =3D start.elapsed(); + self.runtime +=3D elapsed; + + Row { + name, + stats: Stats::new(&mut self.timings), + runtime: Runtime(elapsed), + } + } + + /// The wall time of every run so far. + pub fn runtime(&self) -> Runtime { + Runtime(self.runtime) + } +} + +#[macros::kunit_tests(rust_bench)] +mod tests { + use super::*; + + #[test] + fn stats() { + let odd =3D Stats::new(&mut [5, 1, 9]); + assert_eq!((odd.min, odd.median, odd.max, odd.mean), (1, 5, 9, 5)); + // Median check for even samples. + let med =3D Stats::new(&mut [4, 1, 9, 5]); + assert_eq!(med.median, 4); + } +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 1e3c8d3051e53..95162ab0c3f13 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -48,6 +48,7 @@ #[cfg(CONFIG_AUXILIARY_BUS)] pub mod auxiliary; pub mod bitfield; +pub mod bench; pub mod bitmap; pub mod bits; #[cfg(CONFIG_BLOCK)] --=20 2.55.0 From nobody Thu Sep 24 14:25:40 2026 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-alma10-1.taild15c8.ts.net [100.103.45.18]) (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 1580A3A2549; Wed, 23 Sep 2026 21:00:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=100.103.45.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790197258; cv=none; b=erGCm7yd/6rXy0lwss+sRmRGd02yO7tF0c5plW3UQTGquV9ecbyA6KccMbOxjnTGCp3yoEHIUvHoo7wasp2mMwaAOykLrETizUtL4SzAaKCsAy6lo+Peg/hqx1GQ8wcRTfqwDtO1sF+mSXlgvIztwe3fHlIktZ2nRtevK9IyL2k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790197258; c=relaxed/simple; bh=8wEnluq+UqNYgeUnrCUYgKmNvv1HVw7OQr3xMl1COYA=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=aeAcOKBp6lyu4cCx66JxOatepGPnr6lvlcBzJ6stCveT25FAcF1zahHmhT2/+RSTMAd6hu5Ta0YlluS417zXnWhF/wa/AxR2hJPwU1vKwwKHkTMNvWRT8uCvWlM041MYxceJN66CPLSRKugK65wV02lNPL9lg3cjOQlc2BOnlpM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=WrCL0n/6; arc=none smtp.client-ip=100.103.45.18 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="WrCL0n/6" Received: by smtp.kernel.org (Postfix) with ESMTPSA id 517041F00893; Wed, 23 Sep 2026 21:00:52 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1790197256; bh=ioG8DeDkIWhii+oaP/gPrUhrxmsuwyWQyEPe7wIpnog=; h=From:Date:Subject:References:In-Reply-To:To:Cc; b=WrCL0n/6SPEx7ryO8BEKPZrtHEOdo5ZMMehcDJYbaxq6K75y1pXvfulYDR7s3YEf1 XtfxQHJNrTBSp3qqJnC/iKTrfXOzMtT8CU2XiTRoCTOOLg1RoJWeI/62jJ/HAmH0/L E1chYQyBhG5f3somSgqBbkzfZIDa5cPdw4YHMbCIR7BIuGvH7p08Xratzwr4oExDt1 hQP1ULqZ44an89UOEAVosRsGYK5pkaPJpVJ0DlOhQzITAgrraCD3WcbIEXnISE/11N Fjg2qbFYslm9aYP5lXNVw3LKGcmPT3N0s16um5044fVVhjivlm1x0rnz3CTKZnuayz KleUV0BSuGp2A== From: Daniel Gomez Date: Wed, 23 Sep 2026 23:00:29 +0200 Subject: [PATCH 3/3] lib/xarray_benchmark_rust: add module 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 Message-Id: <20260923-rxarray-next-v1-3-92eedf185649@samsung.com> References: <20260923-rxarray-next-v1-0-92eedf185649@samsung.com> In-Reply-To: <20260923-rxarray-next-v1-0-92eedf185649@samsung.com> To: "Matthew Wilcox (Oracle)" , Miguel Ojeda , Boqun Feng , Gary Guo , =?utf-8?q?Bj=C3=B6rn_Roy_Baron?= , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , Danilo Krummrich , Daniel Almeida , Tamir Duberstein , Alexandre Courbot , =?utf-8?q?Onur_=C3=96zkan?= , Daniel Gomez , Andrew Morton Cc: Julia Lawall , Corinn Tiffany , "Liam R. Howlett" , Philipp Stanner , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Samsung GOST , Daniel Gomez X-Mailer: b4 0.16-dev X-Developer-Signature: v=1; a=ed25519-sha256; t=1790197237; l=6084; i=da.gomez@samsung.com; s=20240621; h=from:subject:message-id; bh=crzr6czWHzua1jHtCHZnKDKjJI+hbXBW4nz5MNNeqNo=; b=NTQzHgFV74MvsOXCFK1JcbxyZcwkOY+k+Llf5HUEa/dvS/QlWAPAqVrng63T2Dpm+yfkpugka HPmqYlQBkc2BziTE1FGpop+WQ7HxJB62wpij+s1+SakvAI8WyG86D6P X-Developer-Key: i=da.gomez@samsung.com; a=ed25519; pk=BqYk31UHkmv0WZShES6pIZcdmPPGay5LbzifAdZ2Ia4= From: Daniel Gomez Benchmark XArray Rust APIs using `kernel::bench`. Assisted-by: LLM Signed-off-by: Daniel Gomez --- MAINTAINERS | 1 + lib/Kconfig.debug | 10 ++++ lib/Makefile | 1 + lib/xarray_benchmark_rust.rs | 117 +++++++++++++++++++++++++++++++++++++++= ++++ 4 files changed, 129 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index b8bdfe9e22226..f6e45a88475b0 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -29690,6 +29690,7 @@ W: https://rust-for-linux.com B: https://github.com/Rust-for-Linux/linux/issues C: https://rust-for-linux.zulipchat.com T: git git://git.kernel.org/pub/scm/linux/kernel/git/da.gomez/linux.git rx= array-next +F: lib/xarray_benchmark_rust.rs F: rust/kernel/bench.rs F: rust/kernel/rxarray.rs =20 diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 134b15a44625e..6e008f657cd4d 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2667,6 +2667,16 @@ config FIND_BIT_BENCHMARK_RUST =20 If unsure, say N. =20 +config XARRAY_BENCHMARK_RUST + tristate "Benchmark the XArray Rust APIs" + depends on RUST + help + This builds the "xarray_benchmark_rust" module. It runs the same + workloads through the Rust abstraction of the C XArray (kernel::xarray), + and through the Rust XArray implementation (kernel::rxarray). + + If unsure, say N. + config TEST_FIRMWARE tristate "Test firmware loading via userspace interface" depends on FW_LOADER diff --git a/lib/Makefile b/lib/Makefile index dfab958327c5c..9401f5146592e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -66,6 +66,7 @@ obj-y +=3D kstrtox.o obj-$(CONFIG_FIND_BIT_BENCHMARK) +=3D find_bit_benchmark.o obj-$(CONFIG_REGION_ALLOC_BENCHMARK) +=3D region_alloc_benchmark.o obj-$(CONFIG_FIND_BIT_BENCHMARK_RUST) +=3D find_bit_benchmark_rust.o +obj-$(CONFIG_XARRAY_BENCHMARK_RUST) +=3D xarray_benchmark_rust.o obj-$(CONFIG_TEST_BPF) +=3D test_bpf.o test_dhry-objs :=3D dhry_1.o dhry_2.o dhry_run.o obj-$(CONFIG_TEST_DHRY) +=3D test_dhry.o diff --git a/lib/xarray_benchmark_rust.rs b/lib/xarray_benchmark_rust.rs new file mode 100644 index 0000000000000..fa69b975d8d9f --- /dev/null +++ b/lib/xarray_benchmark_rust.rs @@ -0,0 +1,117 @@ +// SPDX-License-Identifier: GPL-2.0 +// +//! Benchmark for the XArray Rust APIs. + +use kernel::{ + bench::{self, Bencher}, + prelude::*, + rxarray::{self, XArray4, XArray6}, + time::{Delta, Instant, Monotonic}, + xarray::{self, AllocKind}, // +}; + +/// Stores integer `entries` at `0..entries` in the empty `xa` and returns= the time taken. +fn store_int( + mut xa: rxarray::XArray, SHIFT, SIZE>, + entries: usize, +) -> Delta { + let time =3D Instant::::now(); + for i in 0..entries { + let entry =3D rxarray::Entry::try_int(i * 10).expect("the value fi= ts in an integer entry"); + xa.store(i, entry, GFP_KERNEL).expect("store"); + } + time.elapsed() +} + +/// Stores pointer `entries` at `0..entries` in the empty `xa` and returns= the time taken. +fn store_ptr( + mut xa: rxarray::XArray, SHIFT, SIZE>, + entries: usize, +) -> Delta { + let time =3D Instant::::now(); + for i in 0..entries { + let entry =3D rxarray::Entry::Pointer(KBox::new(i as u64, GFP_KERN= EL).expect("allocation")); + xa.store(i, entry, GFP_KERNEL).expect("store"); + } + time.elapsed() +} + +/// Allocates the empty C XArray that [`store_ptr_xarray`] stores into. +fn new_ptr_xarray() -> Pin>>> { + KBox::pin_init(xarray::XArray::new(AllocKind::Alloc), GFP_KERNEL).expe= ct("allocation") +} + +/// Stores pointer `entries` at `0..entries` in the empty C XArray `xa` an= d returns the +/// time taken. +fn store_ptr_xarray(xa: Pin>>>, entries: usi= ze) -> Delta { + let time =3D Instant::::now(); + for i in 0..entries { + let value =3D KBox::new(i as u64, GFP_KERNEL).expect("allocation"); + xa.lock() + .store(i, value, GFP_KERNEL) + .map_err(|e| e.error) + .expect("store"); + } + time.elapsed() +} + +/// Runs every benchmark. +fn benchmark(samples: usize, entries: usize) -> Result { + let mut bench =3D Bencher::new(samples, entries)?; + + pr_info!("{samples} samples x {entries} entries, ns per sample:\n"); + pr_info!("{}\n", bench::Heading); + pr_info!( + "{}\n", + bench.run("store_int_rxarray4", XArray4::>::new, store_i= nt) + ); + pr_info!( + "{}\n", + bench.run("store_int_rxarray6", XArray6::>::new, store_i= nt) + ); + pr_info!( + "{}\n", + bench.run("store_ptr_rxarray4", XArray4::>::new, store_p= tr) + ); + pr_info!( + "{}\n", + bench.run("store_ptr_rxarray6", XArray6::>::new, store_p= tr) + ); + pr_info!( + "{}\n", + bench.run("store_ptr_xarray", new_ptr_xarray, store_ptr_xarray) + ); + pr_info!("total runtime {}\n", bench.runtime()); + Ok(()) +} + +/// The benchmark module. +struct Benchmark; + +impl kernel::Module for Benchmark { + fn init(_module: &'static ThisModule) -> Result { + let samples =3D module_parameters::samples.value(); + let entries =3D module_parameters::entries.value(); + benchmark(samples, entries)?; + + Ok(Benchmark) + } +} + +module! { + type: Benchmark, + name: "xarray_benchmark_rust", + authors: ["Daniel Gomez "], + description: "Benchmark: XArray", + license: "GPL v2", + params: { + samples: usize { + default: 100, + description: "Timed runs per benchmark", + }, + entries: usize { + default: 100_000, + description: "Entries stored per run", + }, + }, +} --=20 2.55.0