[13/13] rust: sync: introduce `LockedBy`

  From: Wedson Almeida Filho <walmeida@microsoft.com>

This allows us to have data protected by a lock despite not being
wrapped by it. Access is granted by providing evidence that the lock is
held by the caller.

Signed-off-by: Wedson Almeida Filho <walmeida@microsoft.com>
---
 rust/kernel/sync.rs           |   2 +
 rust/kernel/sync/lock.rs      |   2 +-
 rust/kernel/sync/locked_by.rs | 126 ++++++++++++++++++++++++++++++++++
 3 files changed, 129 insertions(+), 1 deletion(-)
 create mode 100644 rust/kernel/sync/locked_by.rs
  

On 30.03.23 06:39, Wedson Almeida Filho wrote:
> From: Wedson Almeida Filho <walmeida@microsoft.com>
>
> This allows us to have data protected by a lock despite not being
> wrapped by it. Access is granted by providing evidence that the lock is
> held by the caller.
>
> Signed-off-by: Wedson Almeida Filho <walmeida@microsoft.com>
> ---
>   rust/kernel/sync.rs           |   2 +
>   rust/kernel/sync/lock.rs      |   2 +-
>   rust/kernel/sync/locked_by.rs | 126 ++++++++++++++++++++++++++++++++++
>   3 files changed, 129 insertions(+), 1 deletion(-)
>   create mode 100644 rust/kernel/sync/locked_by.rs
>
> diff --git a/rust/kernel/sync.rs b/rust/kernel/sync.rs
> index d6dd0e2c1678..f8edb6d0d794 100644
> --- a/rust/kernel/sync.rs
> +++ b/rust/kernel/sync.rs
> @@ -10,10 +10,12 @@ use crate::types::Opaque;
>   mod arc;
>   mod condvar;
>   pub mod lock;
> +mod locked_by;
>
>   pub use arc::{Arc, ArcBorrow, UniqueArc};
>   pub use condvar::CondVar;
>   pub use lock::{mutex::Mutex, spinlock::SpinLock};
> +pub use locked_by::LockedBy;
>
>   /// Represents a lockdep class. It's a wrapper around C's `lock_class_key`.
>   #[repr(transparent)]
> diff --git a/rust/kernel/sync/lock.rs b/rust/kernel/sync/lock.rs
> index f52ba9ab1b70..51c996ca2109 100644
> --- a/rust/kernel/sync/lock.rs
> +++ b/rust/kernel/sync/lock.rs
> @@ -111,7 +111,7 @@ pub struct Lock<T: ?Sized, B: Backend> {
>       _pin: PhantomPinned,
>
>       /// The data protected by the lock.
> -    data: UnsafeCell<T>,
> +    pub(crate) data: UnsafeCell<T>,
>   }
>
>   // SAFETY: `Lock` can be transferred across thread boundaries iff the data it protects can.
> diff --git a/rust/kernel/sync/locked_by.rs b/rust/kernel/sync/locked_by.rs
> new file mode 100644
> index 000000000000..cbfd4e84b770
> --- /dev/null
> +++ b/rust/kernel/sync/locked_by.rs
> @@ -0,0 +1,126 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! A wrapper for data protected by a lock that does not wrap it.
> +
> +use super::{lock::Backend, lock::Lock};
> +use core::{cell::UnsafeCell, ptr};
> +
> +/// Allows access to some data to be serialised by a lock that does not wrap it.
> +///
> +/// In most cases, data protected by a lock is wrapped by the appropriate lock type, e.g.,
> +/// [`super::Mutex`] or [`super::SpinLock`]. [`LockedBy`] is meant for cases when this is not
> +/// possible. For example, if a container has a lock and some data in the contained elements needs
> +/// to be protected by the same lock.
> +///
> +/// [`LockedBy`] wraps the data in lieu of another locking primitive, and only allows access to it
> +/// when the caller shows evidence that the 'external' lock is locked.
> +///
> +/// # Examples
> +///
> +/// The following is an example for illustrative purposes: `InnerDirectory::bytes_used` is an
> +/// aggregate of all `InnerFile::bytes_used` and must be kept consistent; so we wrap `InnerFile` in
> +/// a `LockedBy` so that it shares a lock with `InnerDirectory`. This allows us to enforce at
> +/// compile-time that access to `InnerFile` is only granted when an `InnerDirectory` is also
> +/// locked; we enforce at run time that the right `InnerDirectory` is locked.
> +///
> +/// ```
> +/// use kernel::sync::{LockedBy, Mutex};
> +///
> +/// struct InnerFile {
> +///     bytes_used: u64,
> +/// }
> +///
> +/// struct File {
> +///     _ino: u32,
> +///     inner: LockedBy<InnerFile, InnerDirectory>,
> +/// }
> +///
> +/// struct InnerDirectory {
> +///     /// The sum of the bytes used by all files.
> +///     bytes_used: u64,
> +///     _files: Vec<File>,
> +/// }
> +///
> +/// struct Directory {
> +///     _ino: u32,
> +///     inner: Mutex<InnerDirectory>,
> +/// }
> +///
> +/// /// Prints `bytes_used` from both the directory and file.
> +/// fn print_bytes_used(dir: &Directory, file: &File) {
> +///     let guard = dir.inner.lock();
> +///     let inner_file = file.inner.access(&guard);
> +///     pr_info!("{} {}", guard.bytes_used, inner_file.bytes_used);
> +/// }
> +///
> +/// /// Increments `bytes_used` for both the directory and file.
> +/// fn inc_bytes_used(dir: &Directory, file: &File) {
> +///     let mut guard = dir.inner.lock();
> +///     guard.bytes_used += 10;
> +///
> +///     let file_inner = file.inner.access_mut(&mut guard);

Missing deref (`*`) in front of `guard`.

> +///     file_inner.bytes_used += 10;
> +/// }
> +///
> +/// /// Creates a new file.
> +/// fn new_file(ino: u32, dir: &Directory) -> File {
> +///     File {
> +///         _ino: ino,
> +///         inner: LockedBy::new(&dir.inner, InnerFile { bytes_used: 0 }),
> +///     }
> +/// }
> +/// ```
> +pub struct LockedBy<T: ?Sized, U: ?Sized> {
> +    owner: *const U,
> +    data: UnsafeCell<T>,
> +}
> +
> +// SAFETY: `LockedBy` can be transferred across thread boundaries iff the data it protects can.
> +unsafe impl<T: ?Sized + Send, U: ?Sized> Send for LockedBy<T, U> {}
> +
> +// SAFETY: `LockedBy` serialises the interior mutability it provides, so it is `Sync` as long as the
> +// data it protects is `Send`.
> +unsafe impl<T: ?Sized + Send, U: ?Sized> Sync for LockedBy<T, U> {}
> +
> +impl<T, U: ?Sized> LockedBy<T, U> {
> +    /// Constructs a new instance of [`LockedBy`].
> +    ///
> +    /// It stores a raw pointer to the owner that is never dereferenced. It is only used to ensure
> +    /// that the right owner is being used to access the protected data. If the owner is freed, the
> +    /// data becomes inaccessible; if another instance of the owner is allocated *on the same
> +    /// memory location*, the data becomes accessible again: none of this affects memory safety
> +    /// because in any case at most one thread (or CPU) can access the protected data at a time.
> +    pub fn new(owner: &Lock<U, impl Backend>, data: T) -> Self {
> +        Self {
> +            owner: owner.data.get(),
> +            data: UnsafeCell::new(data),
> +        }
> +    }
> +}
> +
> +impl<T: ?Sized, U: ?Sized> LockedBy<T, U> {
> +    /// Returns a reference to the protected data when the caller provides evidence (via a
> +    /// reference) that the owner is locked.
> +    pub fn access<'a>(&'a self, owner: &'a U) -> &'a T {
> +        if !ptr::eq(owner, self.owner) {
> +            panic!("mismatched owners");
> +        }
> +
> +        // SAFETY: `owner` is evidence that the owner is locked.
> +        unsafe { &*self.data.get() }
> +    }
> +
> +    /// Returns a mutable reference to the protected data when the caller provides evidence (via a
> +    /// mutable owner) that the owner is locked mutably.
> +    ///
> +    /// Showing a mutable reference to the owner is sufficient because we know no other references
> +    /// can exist to it.
> +    pub fn access_mut<'a>(&'a self, owner: &'a mut U) -> &'a mut T {
> +        if !ptr::eq(owner, self.owner) {
> +            panic!("mismatched owners");
> +        }
> +
> +        // SAFETY: `owner` is evidence that there is only one reference to the owner.
> +        unsafe { &mut *self.data.get() }
> +    }
> +}
> --
> 2.34.1
>

What happens if the the protected data `U` is a ZST? Then the address
comparing will not work, since all ZST references have the same address.
For example:

     struct Outer {
         mtx: Mutex<()>,
         inners: Vec<Inner>,
     }

     struct Inner {
         count: LockedBy<usize, ()>,
     }

     fn evil(inner: &Inner) {
         // can create two mutable references at the same time:
         let a = inner.count.access_mut(&mut ());
         let b = inner.count.access_mut(&mut ());
         core::mem::swap(a, b);
     }

Maybe prevent this by checking for `assert!(mem::size_of::<U>() != 0);`
in the `new` function? Though I am not sure if a ZST is the only way for
values to share addresses.

--
Cheers,
Benno
  

On 30.03.23 13:28, Benno Lossin wrote:
> What happens if the the protected data `U` is a ZST? Then the address
> comparing will not work, since all ZST references have the same address.
> For example:
>
>       struct Outer {
>           mtx: Mutex<()>,
>           inners: Vec<Inner>,
>       }
>
>       struct Inner {
>           count: LockedBy<usize, ()>,
>       }
>
>       fn evil(inner: &Inner) {
>           // can create two mutable references at the same time:
>           let a = inner.count.access_mut(&mut ());
>           let b = inner.count.access_mut(&mut ());
>           core::mem::swap(a, b);
>       }

Sorry the example I provided does not actually work, since `&mut ()`
refers to a place on the stack. I found a new example that shows ZSTs
are still problematic:

     struct Outer {
         mtx1: Mutex<()>,
         mtx2: Mutex<()>,
         inners: Vec<Inner>,
     }

     struct Inner {
         count: LockedBy<usize, ()>,
     }

     fn new_inner(outer: &Outer) -> Inner {
         Inner { count: LockedBy::new(&outer.mtx1, 0) }
     }

     fn evil(outer: &Outer) {
         let inner = outer.inners.get(0).unwrap();
         let mut guard1 = outer.mtx1.lock();
         let mut guard2 = outer.mtx2.lock();
	// The pointee of `guard1` and `guard2` have the same address.
         let ref1 = inner.count.access_mut(&mut *guard1);
         let ref2 = inner.count.access_mut(&mut *guard2);
         mem::swap(ref1, ref2);
     }

--
Cheers,
Benno
  

Hey Benno,

Thanks for reviewing!

On Thu, 30 Mar 2023 at 08:29, Benno Lossin <y86-dev@protonmail.com> wrote:
>
> On 30.03.23 06:39, Wedson Almeida Filho wrote:
> > From: Wedson Almeida Filho <walmeida@microsoft.com>
> >
> > This allows us to have data protected by a lock despite not being
> > wrapped by it. Access is granted by providing evidence that the lock is
> > held by the caller.
> >
> > Signed-off-by: Wedson Almeida Filho <walmeida@microsoft.com>
> > ---
> >   rust/kernel/sync.rs           |   2 +
> >   rust/kernel/sync/lock.rs      |   2 +-
> >   rust/kernel/sync/locked_by.rs | 126 ++++++++++++++++++++++++++++++++++
> >   3 files changed, 129 insertions(+), 1 deletion(-)
> >   create mode 100644 rust/kernel/sync/locked_by.rs
> >
> > diff --git a/rust/kernel/sync.rs b/rust/kernel/sync.rs
> > index d6dd0e2c1678..f8edb6d0d794 100644
> > --- a/rust/kernel/sync.rs
> > +++ b/rust/kernel/sync.rs
> > @@ -10,10 +10,12 @@ use crate::types::Opaque;
> >   mod arc;
> >   mod condvar;
> >   pub mod lock;
> > +mod locked_by;
> >
> >   pub use arc::{Arc, ArcBorrow, UniqueArc};
> >   pub use condvar::CondVar;
> >   pub use lock::{mutex::Mutex, spinlock::SpinLock};
> > +pub use locked_by::LockedBy;
> >
> >   /// Represents a lockdep class. It's a wrapper around C's `lock_class_key`.
> >   #[repr(transparent)]
> > diff --git a/rust/kernel/sync/lock.rs b/rust/kernel/sync/lock.rs
> > index f52ba9ab1b70..51c996ca2109 100644
> > --- a/rust/kernel/sync/lock.rs
> > +++ b/rust/kernel/sync/lock.rs
> > @@ -111,7 +111,7 @@ pub struct Lock<T: ?Sized, B: Backend> {
> >       _pin: PhantomPinned,
> >
> >       /// The data protected by the lock.
> > -    data: UnsafeCell<T>,
> > +    pub(crate) data: UnsafeCell<T>,
> >   }
> >
> >   // SAFETY: `Lock` can be transferred across thread boundaries iff the data it protects can.
> > diff --git a/rust/kernel/sync/locked_by.rs b/rust/kernel/sync/locked_by.rs
> > new file mode 100644
> > index 000000000000..cbfd4e84b770
> > --- /dev/null
> > +++ b/rust/kernel/sync/locked_by.rs
> > @@ -0,0 +1,126 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +//! A wrapper for data protected by a lock that does not wrap it.
> > +
> > +use super::{lock::Backend, lock::Lock};
> > +use core::{cell::UnsafeCell, ptr};
> > +
> > +/// Allows access to some data to be serialised by a lock that does not wrap it.
> > +///
> > +/// In most cases, data protected by a lock is wrapped by the appropriate lock type, e.g.,
> > +/// [`super::Mutex`] or [`super::SpinLock`]. [`LockedBy`] is meant for cases when this is not
> > +/// possible. For example, if a container has a lock and some data in the contained elements needs
> > +/// to be protected by the same lock.
> > +///
> > +/// [`LockedBy`] wraps the data in lieu of another locking primitive, and only allows access to it
> > +/// when the caller shows evidence that the 'external' lock is locked.
> > +///
> > +/// # Examples
> > +///
> > +/// The following is an example for illustrative purposes: `InnerDirectory::bytes_used` is an
> > +/// aggregate of all `InnerFile::bytes_used` and must be kept consistent; so we wrap `InnerFile` in
> > +/// a `LockedBy` so that it shares a lock with `InnerDirectory`. This allows us to enforce at
> > +/// compile-time that access to `InnerFile` is only granted when an `InnerDirectory` is also
> > +/// locked; we enforce at run time that the right `InnerDirectory` is locked.
> > +///
> > +/// ```
> > +/// use kernel::sync::{LockedBy, Mutex};
> > +///
> > +/// struct InnerFile {
> > +///     bytes_used: u64,
> > +/// }
> > +///
> > +/// struct File {
> > +///     _ino: u32,
> > +///     inner: LockedBy<InnerFile, InnerDirectory>,
> > +/// }
> > +///
> > +/// struct InnerDirectory {
> > +///     /// The sum of the bytes used by all files.
> > +///     bytes_used: u64,
> > +///     _files: Vec<File>,
> > +/// }
> > +///
> > +/// struct Directory {
> > +///     _ino: u32,
> > +///     inner: Mutex<InnerDirectory>,
> > +/// }
> > +///
> > +/// /// Prints `bytes_used` from both the directory and file.
> > +/// fn print_bytes_used(dir: &Directory, file: &File) {
> > +///     let guard = dir.inner.lock();
> > +///     let inner_file = file.inner.access(&guard);
> > +///     pr_info!("{} {}", guard.bytes_used, inner_file.bytes_used);
> > +/// }
> > +///
> > +/// /// Increments `bytes_used` for both the directory and file.
> > +/// fn inc_bytes_used(dir: &Directory, file: &File) {
> > +///     let mut guard = dir.inner.lock();
> > +///     guard.bytes_used += 10;
> > +///
> > +///     let file_inner = file.inner.access_mut(&mut guard);
>
> Missing deref (`*`) in front of `guard`.

`Deref` coercion obviates the need for an explicit dereference. This
works as is.

> > +///     file_inner.bytes_used += 10;
> > +/// }
> > +///
> > +/// /// Creates a new file.
> > +/// fn new_file(ino: u32, dir: &Directory) -> File {
> > +///     File {
> > +///         _ino: ino,
> > +///         inner: LockedBy::new(&dir.inner, InnerFile { bytes_used: 0 }),
> > +///     }
> > +/// }
> > +/// ```
> > +pub struct LockedBy<T: ?Sized, U: ?Sized> {
> > +    owner: *const U,
> > +    data: UnsafeCell<T>,
> > +}
> > +
> > +// SAFETY: `LockedBy` can be transferred across thread boundaries iff the data it protects can.
> > +unsafe impl<T: ?Sized + Send, U: ?Sized> Send for LockedBy<T, U> {}
> > +
> > +// SAFETY: `LockedBy` serialises the interior mutability it provides, so it is `Sync` as long as the
> > +// data it protects is `Send`.
> > +unsafe impl<T: ?Sized + Send, U: ?Sized> Sync for LockedBy<T, U> {}
> > +
> > +impl<T, U: ?Sized> LockedBy<T, U> {
> > +    /// Constructs a new instance of [`LockedBy`].
> > +    ///
> > +    /// It stores a raw pointer to the owner that is never dereferenced. It is only used to ensure
> > +    /// that the right owner is being used to access the protected data. If the owner is freed, the
> > +    /// data becomes inaccessible; if another instance of the owner is allocated *on the same
> > +    /// memory location*, the data becomes accessible again: none of this affects memory safety
> > +    /// because in any case at most one thread (or CPU) can access the protected data at a time.
> > +    pub fn new(owner: &Lock<U, impl Backend>, data: T) -> Self {
> > +        Self {
> > +            owner: owner.data.get(),
> > +            data: UnsafeCell::new(data),
> > +        }
> > +    }
> > +}
> > +
> > +impl<T: ?Sized, U: ?Sized> LockedBy<T, U> {
> > +    /// Returns a reference to the protected data when the caller provides evidence (via a
> > +    /// reference) that the owner is locked.
> > +    pub fn access<'a>(&'a self, owner: &'a U) -> &'a T {
> > +        if !ptr::eq(owner, self.owner) {
> > +            panic!("mismatched owners");
> > +        }
> > +
> > +        // SAFETY: `owner` is evidence that the owner is locked.
> > +        unsafe { &*self.data.get() }
> > +    }
> > +
> > +    /// Returns a mutable reference to the protected data when the caller provides evidence (via a
> > +    /// mutable owner) that the owner is locked mutably.
> > +    ///
> > +    /// Showing a mutable reference to the owner is sufficient because we know no other references
> > +    /// can exist to it.
> > +    pub fn access_mut<'a>(&'a self, owner: &'a mut U) -> &'a mut T {
> > +        if !ptr::eq(owner, self.owner) {
> > +            panic!("mismatched owners");
> > +        }
> > +
> > +        // SAFETY: `owner` is evidence that there is only one reference to the owner.
> > +        unsafe { &mut *self.data.get() }
> > +    }
> > +}
> > --
> > 2.34.1
> >
>
> What happens if the the protected data `U` is a ZST? Then the address
> comparing will not work, since all ZST references have the same address.

Indeed SZTs are problematic. I'll add a restriction to rule them out.

> For example:
>
>      struct Outer {
>          mtx: Mutex<()>,
>          inners: Vec<Inner>,
>      }
>
>      struct Inner {
>          count: LockedBy<usize, ()>,
>      }
>
>      fn evil(inner: &Inner) {
>          // can create two mutable references at the same time:
>          let a = inner.count.access_mut(&mut ());
>          let b = inner.count.access_mut(&mut ());
>          core::mem::swap(a, b);
>      }
>
> Maybe prevent this by checking for `assert!(mem::size_of::<U>() != 0);`
> in the `new` function? Though I am not sure if a ZST is the only way for
> values to share addresses.

I'll add such an assert a part of a `const` inside an impl block so
that we get it to fail at compile time if misused.

>
> --
> Cheers,
> Benno
>
>
  

On Thu, 30 Mar 2023 at 08:45, Benno Lossin <y86-dev@protonmail.com> wrote:
>
> On 30.03.23 13:28, Benno Lossin wrote:
>      struct Outer {
>          mtx1: Mutex<()>,
>          mtx2: Mutex<()>,
>          inners: Vec<Inner>,
>      }
>
>      struct Inner {
>          count: LockedBy<usize, ()>,
>      }
>
>      fn new_inner(outer: &Outer) -> Inner {
>          Inner { count: LockedBy::new(&outer.mtx1, 0) }
>      }
>
>      fn evil(outer: &Outer) {
>          let inner = outer.inners.get(0).unwrap();
>          let mut guard1 = outer.mtx1.lock();
>          let mut guard2 = outer.mtx2.lock();
>         // The pointee of `guard1` and `guard2` have the same address.
>          let ref1 = inner.count.access_mut(&mut *guard1);
>          let ref2 = inner.count.access_mut(&mut *guard2);
>          mem::swap(ref1, ref2);
>      }

This doesn't reproduce the issue because `mtx2` itself is not a ZST
(it contains a `struct mutex` before the data it protects).

Something like the following should reproduce it though:

    struct Outer {
         mtx1: Mutex<()>,
         zst: (),
     }

     fn evil(outer: &Outer) {
         let lb = LockedBy::new(&outer.mtx1, 0u8);
         let value = lb.access(&outer.zst);
         // Accessing "value" without holding `mtx1`.
         pr_info!("{}", *value);
     }
  

On 30.03.23 23:04, Wedson Almeida Filho wrote:
> On Thu, 30 Mar 2023 at 08:45, Benno Lossin <y86-dev@protonmail.com> wrote:
>>
>> On 30.03.23 13:28, Benno Lossin wrote:
>>       struct Outer {
>>           mtx1: Mutex<()>,
>>           mtx2: Mutex<()>,
>>           inners: Vec<Inner>,
>>       }
>>
>>       struct Inner {
>>           count: LockedBy<usize, ()>,
>>       }
>>
>>       fn new_inner(outer: &Outer) -> Inner {
>>           Inner { count: LockedBy::new(&outer.mtx1, 0) }
>>       }
>>
>>       fn evil(outer: &Outer) {
>>           let inner = outer.inners.get(0).unwrap();
>>           let mut guard1 = outer.mtx1.lock();
>>           let mut guard2 = outer.mtx2.lock();
>>          // The pointee of `guard1` and `guard2` have the same address.
>>           let ref1 = inner.count.access_mut(&mut *guard1);
>>           let ref2 = inner.count.access_mut(&mut *guard2);
>>           mem::swap(ref1, ref2);
>>       }
>
> This doesn't reproduce the issue because `mtx2` itself is not a ZST
> (it contains a `struct mutex` before the data it protects).
>
> Something like the following should reproduce it though:
>
>      struct Outer {
>           mtx1: Mutex<()>,
>           zst: (),
>       }
>
>       fn evil(outer: &Outer) {
>           let lb = LockedBy::new(&outer.mtx1, 0u8);
>           let value = lb.access(&outer.zst);
>           // Accessing "value" without holding `mtx1`.
>           pr_info!("{}", *value);
>       }

You are correct, but in your example you also cannot be sure that it
works, since the layout of the `Mutex` and `Outer` is `repr(Rust)`.
And so you cannot be sure that `zst` has the same address as `value`
inside of the `Mutex` (since the `struct mutex` could be in between).
But regardless, lets just deny ZSTs in `LockedBy` since the fix is
easy and it would be weird to put a ZST in a lock in the first place.
(Not that you have argued against it)

--
Cheers,
Benno