RCU protected pointers are an atomic pointer that can be loaded and
dereferenced by mulitple RCU readers, but only one updater/writer can
change the value (following a read-copy-update pattern usually).
This is useful in the case where data is read-mostly. The rationale of
this patch is to provide a proof of concept on how RCU should be exposed
to the Rust world, and it also serves as an example for atomic usage.
Similar mechanisms like ArcSwap [1] are already widely used.
Provide a `Rcu<P>` type with an atomic pointer implementation. `P` has
to be a `ForeignOwnable`, which means the ownership of a object can be
represented by a pointer-size value.
`Rcu::dereference()` requires a RCU Guard, which means dereferencing is
only valid under RCU read lock protection.
`Rcu::read_copy_update()` is the operation for updaters, it requries a
`Pin<&mut Self>` for exclusive accesses, since RCU updaters are normally
exclusive with each other.
A lot of RCU functionalities including asynchronously free (call_rcu()
and kfree_rcu()) are still missing, and will be the future work.
Also, we still need language changes like field projection [2] to
provide better ergonomic.
Acknowledgment: this work is based on a lot of productive discussions
and hard work from others, these are the ones I can remember (sorry if I
forgot your contribution):
* Wedson started the work on RCU field projection and Benno followed it
up and had been working on it as a more general language feature.
Also, Gary's field-projection repo [3] has been used as an example for
related discussions.
* During Kangrejos 2023 [4], Gary, Benno and Alice provided a lot of
feedbacks on the talk from Paul and me: "If you want to use RCU in
Rust for Linux kernel..."
* During a recent discussion among Benno, Paul and me, Benno suggested
using `Pin<&mut>` to guarantee the exclusive access on updater
operations.
Link: https://crates.io/crates/arc-swap [1]
Link: https://rust-lang.zulipchat.com/#narrow/channel/213817-t-lang/topic/Field.20Projections/near/474648059 [2]
Link: https://github.com/nbdd0121/field-projection [3]
Link: https://kangrejos.com/2023 [4]
Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
rust/kernel/sync/rcu.rs | 269 +++++++++++++++++++++++++++++++++++++++-
1 file changed, 268 insertions(+), 1 deletion(-)
diff --git a/rust/kernel/sync/rcu.rs b/rust/kernel/sync/rcu.rs
index 5a35495f69a4..8326b2e0986a 100644
--- a/rust/kernel/sync/rcu.rs
+++ b/rust/kernel/sync/rcu.rs
@@ -5,7 +5,11 @@
//! C header: [`include/linux/rcupdate.h`](srctree/include/linux/rcupdate.h)
use crate::bindings;
-use core::marker::PhantomData;
+use crate::{
+ sync::atomic::{Atomic, Relaxed, Release},
+ types::ForeignOwnable,
+};
+use core::{marker::PhantomData, pin::Pin, ptr::NonNull};
/// Evidence that the RCU read side lock is held on the current thread/CPU.
///
@@ -50,3 +54,266 @@ fn drop(&mut self) {
pub fn read_lock() -> Guard {
Guard::new()
}
+
+/// An RCU protected pointer, the pointed object is protected by RCU.
+///
+/// # Invariants
+///
+/// Either the pointer is null, or it points to a return value of [`P::into_foreign`] and the atomic
+/// variable exclusively owns the pointer.
+pub struct Rcu<P: ForeignOwnable>(Atomic<*mut core::ffi::c_void>, PhantomData<P>);
+
+/// A pointer that has been unpublished, but hasn't waited for a grace period yet.
+///
+/// The pointed object may still have an existing RCU reader. Therefore a grace period is needed to
+/// free the object.
+///
+/// # Invariants
+///
+/// The pointer has to be a return value of [`P::into_foreign`] and [`Self`] exclusively owns the
+/// pointer.
+pub struct RcuOld<P: ForeignOwnable>(NonNull<core::ffi::c_void>, PhantomData<P>);
+
+impl<P: ForeignOwnable> Drop for RcuOld<P> {
+ fn drop(&mut self) {
+ // SAFETY: As long as called in a sleepable context, which should be checked by klint,
+ // `synchronize_rcu()` is safe to call.
+ unsafe {
+ bindings::synchronize_rcu();
+ }
+
+ // SAFETY: `self.0` is a return value of `P::into_foreign()`, so it's safe to call
+ // `from_foreign()` on it. Plus, the above `synchronize_rcu()` guarantees no existing
+ // `ForeignOwnable::borrow()` anymore.
+ let p: P = unsafe { P::from_foreign(self.0.as_ptr()) };
+ drop(p);
+ }
+}
+
+impl<P: ForeignOwnable> Rcu<P> {
+ /// Creates a new RCU pointer.
+ pub fn new(p: P) -> Self {
+ // INVARIANTS: The return value of `p.into_foreign()` is directly stored in the atomic
+ // variable.
+ Self(Atomic::new(p.into_foreign().cast_mut()), PhantomData)
+ }
+
+ /// Dereferences the protected object.
+ ///
+ /// Returns `Some(b)`, where `b` is a reference-like borrowed type, if the pointer is not null,
+ /// otherwise returns `None`.
+ ///
+ /// # Examples
+ ///
+ /// ```rust
+ /// # use kernel::alloc::{flags, KBox};
+ /// use kernel::sync::rcu::{self, Rcu};
+ ///
+ /// let x = Rcu::new(KBox::new(100i32, flags::GFP_KERNEL)?);
+ ///
+ /// let g = rcu::read_lock();
+ /// // Read in under RCU read lock protection.
+ /// let v = x.dereference(&g);
+ ///
+ /// assert_eq!(v, Some(&100i32));
+ ///
+ /// # Ok::<(), Error>(())
+ /// ```
+ ///
+ /// Note the borrowed access can outlive the reference of the [`Rcu<P>`], this is because as
+ /// long as the RCU read lock is held, the pointed object should remain valid.
+ ///
+ /// In the following case, the main thread is responsible for the ownership of `shared`, i.e. it
+ /// will drop it eventually, and a work item can temporarily access the `shared` via `cloned`,
+ /// but the use of the dereferenced object doesn't depend on `cloned`'s existence.
+ ///
+ /// ```rust
+ /// # use kernel::alloc::{flags, KBox};
+ /// # use kernel::workqueue::system;
+ /// # use kernel::sync::{Arc, atomic::{Atomic, Acquire, Release}};
+ /// use kernel::sync::rcu::{self, Rcu};
+ ///
+ /// struct Config {
+ /// a: i32,
+ /// b: i32,
+ /// c: i32,
+ /// }
+ ///
+ /// let config = KBox::new(Config { a: 1, b: 2, c: 3 }, flags::GFP_KERNEL)?;
+ ///
+ /// let shared = Arc::new(Rcu::new(config), flags::GFP_KERNEL)?;
+ /// let cloned = shared.clone();
+ ///
+ /// // Use atomic to simulate a special refcounting.
+ /// static FLAG: Atomic<i32> = Atomic::new(0);
+ ///
+ /// system().try_spawn(flags::GFP_KERNEL, move || {
+ /// let g = rcu::read_lock();
+ /// let v = cloned.dereference(&g).unwrap();
+ /// drop(cloned); // release reference to `shared`.
+ /// FLAG.store(1, Release);
+ ///
+ /// // but still need to access `v`.
+ /// assert_eq!(v.a, 1);
+ /// drop(g);
+ /// });
+ ///
+ /// // Wait until `cloned` dropped.
+ /// while FLAG.load(Acquire) == 0 {
+ /// // SAFETY: Sleep should be safe.
+ /// unsafe { kernel::bindings::schedule(); }
+ /// }
+ ///
+ /// drop(shared);
+ ///
+ /// # Ok::<(), Error>(())
+ /// ```
+ pub fn dereference<'rcu>(&self, _rcu_guard: &'rcu Guard) -> Option<P::Borrowed<'rcu>> {
+ // Ordering: Address dependency pairs with the `store(Release)` in read_copy_update().
+ let ptr = self.0.load(Relaxed);
+
+ if !ptr.is_null() {
+ // SAFETY:
+ // - Since `ptr` is not null, so it has to be a return value of `P::into_foreign()`.
+ // - The returned `Borrowed<'rcu>` cannot outlive the RCU Guar, this guarantees the
+ // return value will only be used under RCU read lock, and the RCU read lock prevents
+ // the pass of a grace period that the drop of `RcuOld` or `Rcu` is waiting for,
+ // therefore no `from_foreign()` will be called for `ptr` as long as `Borrowed` exists.
+ //
+ // CPU 0 CPU 1
+ // ===== =====
+ // { `x` is a reference to Rcu<Box<i32>> }
+ // let g = rcu::read_lock();
+ //
+ // if let Some(b) = x.dereference(&g) {
+ // // drop(g); cannot be done, since `b` is still alive.
+ //
+ // if let Some(old) = x.replace(...) {
+ // // `x` is null now.
+ // println!("{}", b);
+ // }
+ // drop(old):
+ // synchronize_rcu();
+ // drop(g);
+ // // a grace period passed.
+ // // No `Borrowed` exists now.
+ // from_foreign(...);
+ // }
+ Some(unsafe { P::borrow(ptr) })
+ } else {
+ None
+ }
+ }
+
+ /// Read, copy and update the pointer with new value.
+ ///
+ /// Returns `None` if the pointer's old value is null, otherwise returns `Some(old)`, where old
+ /// is a [`RcuOld`] which can be used to free the old object eventually.
+ ///
+ /// The `Pin<&mut Self>` is needed because this function needs the exclusive access to
+ /// [`Rcu<P>`], otherwise two `read_copy_update()`s may get the same old object and double free.
+ /// Using `Pin<&mut Self>` provides the exclusive access that C side requires with the type
+ /// system checking.
+ ///
+ /// Also this has to be `Pin` because a `&mut Self` may allow users to `swap()` safely, that
+ /// will break the atomicity. A [`Rcu<P>`] should be structurally pinned in the struct that
+ /// contains it.
+ ///
+ /// Note that `Pin<&mut Self>` cannot assume noalias here because [`Atomic<T>`] is a
+ /// [`Opaque<T>`] which has the same effect on aliasing rules as [`UnsafePinned`].
+ ///
+ /// [`UnsafePinned`]: https://rust-lang.github.io/rfcs/3467-unsafe-pinned.html
+ pub fn read_copy_update<F>(self: Pin<&mut Self>, f: F) -> Option<RcuOld<P>>
+ where
+ F: FnOnce(Option<P::Borrowed<'_>>) -> Option<P>,
+ {
+ // step 1: READ.
+ // Ordering: Address dependency pairs with the `store(Release)` in read_copy_update().
+ let old_ptr = NonNull::new(self.0.load(Relaxed));
+
+ let old = old_ptr.map(|nonnull| {
+ // SAFETY: Per type invariants `old_ptr` has to be a value return by a previous
+ // `into_foreign()`, and the exclusive reference `self` guarantees that `from_foreign()`
+ // has not been called.
+ unsafe { P::borrow(nonnull.as_ptr()) }
+ });
+
+ // step 2: COPY, or more generally, initializing `new` based on `old`.
+ let new = f(old);
+
+ // step 3: UPDATE.
+ if let Some(new) = new {
+ let new_ptr = new.into_foreign().cast_mut();
+ // Ordering: Pairs with the address dependency in `dereference()` and
+ // `read_copy_update()`.
+ // INVARIANTS: `new.into_foreign()` is directly store into the atomic variable.
+ self.0.store(new_ptr, Release);
+ } else {
+ // Ordering: Setting to a null pointer doesn't need to be Release.
+ // INVARIANTS: The atomic variable is set to be null.
+ self.0.store(core::ptr::null_mut(), Relaxed);
+ }
+
+ // INVARIANTS: The exclusive reference guarantess that the ownership of a previous
+ // `into_foreign()` transferred to the `RcuOld`.
+ Some(RcuOld(old_ptr?, PhantomData))
+ }
+
+ /// Replaces the pointer with new value.
+ ///
+ /// Returns `None` if the pointer's old value is null, otherwise returns `Some(old)`, where old
+ /// is a [`RcuOld`] which can be used to free the old object eventually.
+ ///
+ /// # Examples
+ ///
+ /// ```rust
+ /// use core::pin::pin;
+ /// # use kernel::alloc::{flags, KBox};
+ /// use kernel::sync::rcu::{self, Rcu};
+ ///
+ /// let mut x = pin!(Rcu::new(KBox::new(100i32, flags::GFP_KERNEL)?));
+ /// let q = KBox::new(101i32, flags::GFP_KERNEL)?;
+ ///
+ /// // Read in under RCU read lock protection.
+ /// let g = rcu::read_lock();
+ /// let v = x.dereference(&g);
+ ///
+ /// // Replace with a new object.
+ /// let old = x.as_mut().replace(q);
+ ///
+ /// assert!(old.is_some());
+ ///
+ /// // `v` should still read the old value.
+ /// assert_eq!(v, Some(&100i32));
+ ///
+ /// // New readers should get the new value.
+ /// assert_eq!(x.dereference(&g), Some(&101i32));
+ ///
+ /// drop(g);
+ ///
+ /// // Can free the object outside the read-side critical section.
+ /// drop(old);
+ /// # Ok::<(), Error>(())
+ /// ```
+ pub fn replace(self: Pin<&mut Self>, new: P) -> Option<RcuOld<P>> {
+ self.read_copy_update(|_| Some(new))
+ }
+}
+
+impl<P: ForeignOwnable> Drop for Rcu<P> {
+ fn drop(&mut self) {
+ let ptr = *self.0.get_mut();
+ if !ptr.is_null() {
+ // SAFETY: As long as called in a sleepable context, which should be checked by klint,
+ // `synchronize_rcu()` is safe to call.
+ unsafe {
+ bindings::synchronize_rcu();
+ }
+
+ // SAFETY: `self.0` is a return value of `P::into_foreign()`, so it's safe to call
+ // `from_foreign()` on it. Plus, the above `synchronize_rcu()` guarantees no existing
+ // `ForeignOwnable::borrow()` anymore.
+ drop(unsafe { P::from_foreign(ptr) });
+ }
+ }
+}
--
2.45.2© 2016 - 2024 Red Hat, Inc.