Skip to contentSkip to conversation

Rust XArray

PATCH Superseded Daniel Gomez 2 participants 6 messages Sep 23

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover Rust XArray

We are evaluating Rust for the XArray to test if Rust delivers what it promises for a core kernel data structure, as a consequence of a page cache bug that was dormant for years, left users with a corrupted FS, was difficult to reproduce, and almost prevented the LBS work [1] from being merged. After looking at other XArray-related bugs, I think this particular one represents well the root cause of most XArray bugs:
misuse of the API by its callers.

The XArray's main user is the page cache, but it has many other users and features, such as multi-index, RCU, etc. This initial support does not cover all these features and so, the initial evaluation targets are the ones that use the data structure in the simplest form. For this reason, I would like this series to be considered as a reference Rust implementation (experimental) [2] that we can merge in-tree to let users experiment and evaluate both implementations starting first from Rust
users: null block driver and potentially drm gpu drivers such as tyr. What this series is missing to achieve this initial target is support for both new entry and preload APIs submitted [3] to the Rust XArray bindings.

This series also includes support for a configurable benchmark library to test different types of workloads. I like to think of it as the fio equivalent for kernel data structures. Currently, it has support for sequential write workloads but the idea is to extend it to support read/write sequential/random as well as multithreading workloads.

After this initial work is done, we can continue with the evaluation by adding support for the features as we see fit. My proposal is to start with C FFI and RCU. The C FFI is, IMO, the critical part to know if Rust can help reduce the bugs we keep finding in the use of this data structure, which, except for one case, are found in both Normal and Advanced API variants, but also in the object manipulation the user is responsible for. This work was presented at Kangrejos 2026 last week and some of the feedback included the possibility to add safety annotations on the C side; promote safety contracts and invariants as part of the API documentation so that C users better understand how to call it "safely" because of the benefits of using type-safe Rust language under the hood. Making these contracts explicit as part of the API is something we can add today and even try to auto-generate, or simply by using the Rust function signature as part of the API documentation. Another way Rust helps is with formal verification: Corinn T. and Julia L. are already doing this work on the C API side and their work "Towards Program Verification of the Linux Kernel Library XArray" will be presented at LPC in a few weeks [4]. My understanding is that Rust helps simplify the formal verification work, although this requires formalizing the API usage by users, not only the implementation. So, whether any of these 3 approaches can help reduce bugs on the C boundary side is something to explore throughout the following series and after this initial support lands, where the Rust users automatically benefit from a safe API.

Multi-architecture support was raised as an initial concern [5] when we proposed this topic for discussion earlier this year. We think that is orthogonal work that will happen eventually but that we do not have control over, and that we can keep making progress if we use this as a reference implementation following the gradual support suggested.

In the same thread, we asked which XArray workloads set the performance bar. Considering the scale of users and that some may require specific hardware, we think the best approach is to integrate a benchmark library (included in this series) that allows differential testing of the 2 implementations through the bindings, so they can be tested independently with standard workloads: seq/rand rw, multithreading, etc. While we expect these results to be representative of what users can expect, specific workloads will be considered too at each step. For example, fio for null block; fio and dbench for page cache as well as the in-tree tools/testing/radix-tree/benchmark.c. Once C FFI support lands, we can also extend differential testing from the C caller side. Functional testing is covered by KUnit tests (included in this series) and will further be extended once we have parity with C XArray functionality to support lib/test_xarray.c.

The following table is a summary of the benchmark results on a QEMU instance with 8 cores and 4 GiB of RAM:

1000 samples x 100000 entries, ns per sample:
benchmark min median max mean runtime

store_int_rxarray4      1347510      1366102      2069508      1389890       2.065s
store_int_rxarray6       809970       822036      1327207       840727       1.417s
store_ptr_rxarray4      2292776      2339906      3440329      2381492       3.953s
store_ptr_rxarray6      1687739      1713935      2815930      1744127       3.226s
store_ptr_xarray        2636308      2763015      5184648      2867016       4.494s

Currently, the benchmark shows that storing pointer entries in the XArray6 configuration (store_ptr_rxarray6) is 1.6x faster than through the C XArray bindings. There is no C row for integer entries yet, as the bindings have no value-entry API.

Note that this version does not include all features, so the comparison is against a C XArray (through bindings) doing probably more work per store. And that the result is only significant for Rust callers. The idea of these numbers is to keep them as baseline as we add more features and, once we have parity, compare them side to side with C equivalent benchmarks.

To continue the work, we propose the following roadmap:

For this initial series:
* Core functionality support: store/load/erase [done]
* C's memory footprint optimization: [done]
* Functional testing KUnit [done]
* Benchmark library: bench [done]
* Sequential workload support [done]
* Random and multithread workload support [planned]
* Entry API [planned]
* Preload API [planned]
* rnull integration and A/B benchmark [planned]
* tyr integration and A/B benchmark [planned]

After this initial series, we can proceed working with the following topics as individual and incremental series:
* Pointer provenance
* Small tree optimization (expand/shrink)
* RCU support
* C FFI + null block integration and A/B benchmark
* Mark support
* Tagged pointers support
* lib/test_xarray.c support
* tools/testing/radix-tree/benchmark.c A/B
* Page cache integration and A/B benchmark

A branch with the patches can be found here:
https://git.kernel.org/pub/scm/linux/kernel/git/da.gomez/linux.git/log/?h=rxarray-next

---
Daniel Gomez (3):
rust: rxarray: add rust xarray support
rust: kernel: add bench
lib/xarray_benchmark_rust: add module

 MAINTAINERS                  |   13 +
 lib/Kconfig.debug            |   10 +
 lib/Makefile                 |    1 +
 lib/xarray_benchmark_rust.rs |  117 ++++
 rust/kernel/bench.rs         |  173 ++++++
 rust/kernel/lib.rs           |    2 +
 rust/kernel/rxarray.rs       | 1407 ++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 1723 insertions(+)

---
base-commit: 4cfc5bf97cabf660c04b22ba933d198cc4aa98ec
change-id: 20260922-rxarray-next-f1912366209c

Best regards,

Signature · 1 line
Daniel Gomez <[email protected]>
#1 lore raw

PATCH 1/3 rust: rxarray: add rust xarray support

From: Daniel Gomez <[email protected]>

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.

---
 MAINTAINERS            |   11 +
 rust/kernel/lib.rs     |    1 +
 rust/kernel/rxarray.rs | 1407 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 1419 insertions(+)
MAINTAINERS +11 -0
index c2414447892c2..c40a254c35d3d 100644
@@ -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
 
+XARRAY [RUST]
+M:	Daniel Gomez <[email protected]>
+R:	Andreas Hindborg <[email protected]>
+L:	[email protected]
+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 rxarray-next
+F:	rust/kernel/rxarray.rs
+
 XBOX DVD IR REMOTE
 M:	Benjamin Valentin <[email protected]>
 S:	Maintained
rust/kernel/lib.rs +1 -0
index 4d5c96ddc49c7..1e3c8d3051e53 100644
@@ -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;
rust/kernel/rxarray.rs new file +1407 -0

1,407 lines not on this page · raw message

Signature · 1 line
2.55.0
#2 lore raw

PATCH 2/3 rust: kernel: add bench

In reply to Daniel Gomez

From: Daniel Gomez <[email protected]>

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
---
 MAINTAINERS          |   1 +
 rust/kernel/bench.rs | 173 +++++++++++++++++++++++++++++++++++++++++++++++++++
 rust/kernel/lib.rs   |   1 +
 3 files changed, 175 insertions(+)
MAINTAINERS +1 -0
index c40a254c35d3d..b8bdfe9e22226 100644
@@ -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 rxarray-next
+F:	rust/kernel/bench.rs
 F:	rust/kernel/rxarray.rs
 
 XBOX DVD IR REMOTE
rust/kernel/bench.rs new file +173 -0

173 lines not on this page · raw message

rust/kernel/lib.rs +1 -0
index 1e3c8d3051e53..95162ab0c3f13 100644
@@ -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)]
Signature · 1 line
2.55.0
#3 lore raw

PATCH 3/3 lib/xarray_benchmark_rust: add module

In reply to Daniel Gomez

From: Daniel Gomez <[email protected]>

Benchmark XArray Rust APIs using kernel::bench.

Assisted-by LLM
---
 MAINTAINERS                  |   1 +
 lib/Kconfig.debug            |  10 ++++
 lib/Makefile                 |   1 +
 lib/xarray_benchmark_rust.rs | 117 +++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 129 insertions(+)
MAINTAINERS +1 -0
index b8bdfe9e22226..f6e45a88475b0 100644
@@ -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 rxarray-next
+F:	lib/xarray_benchmark_rust.rs
 F:	rust/kernel/bench.rs
 F:	rust/kernel/rxarray.rs
 
lib/Kconfig.debug +10 -0
index 134b15a44625e..6e008f657cd4d 100644
@@ -2667,6 +2667,16 @@ config FIND_BIT_BENCHMARK_RUST
 
 	  If unsure, say N.
 
+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
lib/Makefile +1 -0
index dfab958327c5c..9401f5146592e 100644
@@ -66,6 +66,7 @@ obj-y += kstrtox.o
 obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
 obj-$(CONFIG_REGION_ALLOC_BENCHMARK) += region_alloc_benchmark.o
 obj-$(CONFIG_FIND_BIT_BENCHMARK_RUST) += find_bit_benchmark_rust.o
+obj-$(CONFIG_XARRAY_BENCHMARK_RUST) += xarray_benchmark_rust.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 test_dhry-objs := dhry_1.o dhry_2.o dhry_run.o
 obj-$(CONFIG_TEST_DHRY) += test_dhry.o
lib/xarray_benchmark_rust.rs new file +117 -0

117 lines not on this page · raw message

Signature · 1 line
2.55.0
#5 lore raw
In reply to Daniel Gomez

Daniel,

Quoted 10 lines · Daniel Gomez

We are evaluating Rust for the XArray to test if Rust delivers what it promises for a core kernel data structure, as a consequence of a page cache bug that was dormant for years, left users with a corrupted FS, was difficult to reproduce, and almost prevented the LBS work [1] from being merged. After looking at other XArray-related bugs, I think this particular one represents well the root cause of most XArray bugs:
misuse of the API by its callers.

Quoted 8 lines

The XArray's main user is the page cache, but it has many other users and features, such as multi-index, RCU, etc. This initial support does not cover all these features and so, the initial evaluation targets are the ones that use the data structure in the simplest form. For this reason, I would like this series to be considered as a reference Rust implementation (experimental) [2] that we can merge in-tree to let users experiment and evaluate both implementations starting first from Rust
users: null block driver and potentially drm gpu drivers such as tyr.

Thanks a lot for working on this! This will be very helpful for Tyr.

Give me some time to go over the code.

— Daniel