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@xxxxxxxxx> --- 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
