[RFC,07/18] rust: drm: mm: Add DRM MM Range Allocator abstraction

  drm_mm provides a simple range allocator, useful for managing virtual
address ranges. Add a Rust abstraction to expose this module to Rust
drivers.

Signed-off-by: Asahi Lina <lina@asahilina.net>
---
 rust/kernel/drm/mm.rs  | 309 +++++++++++++++++++++++++++++++++++++++++++++++++
 rust/kernel/drm/mod.rs |   1 +
 2 files changed, 310 insertions(+)
  

On Tue, Mar 07, 2023 at 11:25:32PM +0900, Asahi Lina wrote:
> drm_mm provides a simple range allocator, useful for managing virtual
> address ranges. Add a Rust abstraction to expose this module to Rust
> drivers.
> 
> Signed-off-by: Asahi Lina <lina@asahilina.net>

In the cover letter you mentioned the design open about embedded the lock
into the rust wrappers.

I think for a first step that's perfectly fine.

Longer term we might want to ramp up some "proof of locking"
infrastructure in Rust, where callers can supply a lock guard and ideally
rust validates at compile time that it's for the right type, and at
runtime (like lockdep) that it's consistent and the callers don't mix up
locks (like using different locks for the same drm_mm allocator).

There's a lot of libraries in the kernel that have this "caller ensures
locking" pattern. drm/sched also has these requirements.

There's two other things I'd like to bring up on this patch though, just
because it's a good example. But they're both really general points that
apply for all the rust wrappers.

Documentation:

In drm we try to document all the interfaces that drivers use with formal
docs. Yes there's some areas that are not great for historical reasons,
but for new stuff and new wrappers we're really trying:

- This helps in telling internal (even across .c files or in rust across
  modules within a crate) from stuff drivers access. Sure you have static
  in C or pub in rust, but that doesn't tell you whether it's public all
  the way to drivers.

- ideally docs have a short intro section that explains the main concepts
  and links to the main data structures and functions. Just to give
  readers a good starting point to explore.

- Linking all the things, so that readers can connect the different parts.
  This is really important in C where e.g. get/put() or any such function
  pairs all needed to be linked together. With rust I'm hoping that
  rustdoc liberally sprinkles links already and we don't have to do this
  as much.

- Short explainers for parameters. For rust this also means type
  parameters, for those even simplified examples of how drivers are
  supposed to use them would help a lot in reading docs & understanding
  concepts.

- Ideally links from the rust to the sphinx side to linke relevant
  chapters together. Often the bigger explanations are in .rst files with
  DOT graphs (kms has a bunch I've added) or similar, and it doesn't make
  that much sense to duplicate all that on the rust side I guess. But it
  needs to be discoverable.

This might be more a discussion topic for the rust people than you
directly. Still needed for the merge-ready patches eventually.

Refcounting vs borrowing:

This is honestly much more the eyebrow raising one than the locking. Very
often on the C side these datastructures all work with borrow semantics,
and you need to explicitly upgrade to a full reference (kref_get or
kref_get_unless_zero, depending whether it's a strong or weak reference)
if you need the object outside of the mutex/lock guard section.

Again I think for now it's ok, but the sales pitch of rust is that it
enables borrow lifetime checking with no runtime cost. Plus viz the vm
cleanup example, if you have too many strong backreferences the cleanup
flow gets complicated. And it would suck if rust drivers have to add
complexity like the openrefcount for the vm example simply because we
can't model the borrow semantics well enough to be safe.

So not something that's really bad here, but if we need to resort to full
refcounting already for simple datastructures then I'm getting a bit
worried about how well rust will cope with the really nasty borrowed
reference tricks we're playing in other areas.

Again more a topic for the rust folks I think than specifically here about
drm_mm wrapping. Just to get things going I think this is fine.

Cheers, Daniel


> ---
>  rust/kernel/drm/mm.rs  | 309 +++++++++++++++++++++++++++++++++++++++++++++++++
>  rust/kernel/drm/mod.rs |   1 +
>  2 files changed, 310 insertions(+)
> 
> diff --git a/rust/kernel/drm/mm.rs b/rust/kernel/drm/mm.rs
> new file mode 100644
> index 000000000000..83e27a7dcc7e
> --- /dev/null
> +++ b/rust/kernel/drm/mm.rs
> @@ -0,0 +1,309 @@
> +// SPDX-License-Identifier: GPL-2.0 OR MIT
> +
> +//! DRM MM range allocator
> +//!
> +//! C header: [`include/linux/drm/drm_mm.h`](../../../../include/linux/drm/drm_mm.h)
> +
> +use crate::{
> +    bindings,
> +    error::{to_result, Result},
> +    str::CStr,
> +    sync::{Arc, LockClassKey, LockIniter, Mutex, UniqueArc},
> +    types::Opaque,
> +};
> +
> +use alloc::boxed::Box;
> +
> +use core::{
> +    marker::{PhantomData, PhantomPinned},
> +    ops::Deref,
> +    pin::Pin,
> +};
> +
> +/// Type alias representing a DRM MM node.
> +pub type Node<A, T> = Pin<Box<NodeData<A, T>>>;
> +
> +/// Trait which must be implemented by the inner allocator state type provided by the user.
> +pub trait AllocInner<T> {
> +    /// Notification that a node was dropped from the allocator.
> +    fn drop_object(&mut self, _start: u64, _size: u64, _color: usize, _object: &mut T) {}
> +}
> +
> +impl<T> AllocInner<T> for () {}
> +
> +/// Wrapper type for a `struct drm_mm` plus user AllocInner object.
> +///
> +/// # Invariants
> +/// The `drm_mm` struct is valid and initialized.
> +struct MmInner<A: AllocInner<T>, T>(Opaque<bindings::drm_mm>, A, PhantomData<T>);
> +
> +/// Represents a single allocated node in the MM allocator
> +pub struct NodeData<A: AllocInner<T>, T> {
> +    node: bindings::drm_mm_node,
> +    mm: Arc<Mutex<MmInner<A, T>>>,
> +    valid: bool,
> +    /// A drm_mm_node needs to be pinned because nodes reference each other in a linked list.
> +    _pin: PhantomPinned,
> +    inner: T,
> +}
> +
> +// SAFETY: Allocator ops take the mutex, and there are no mutable actions on the node.
> +unsafe impl<A: Send + AllocInner<T>, T: Send> Send for NodeData<A, T> {}
> +unsafe impl<A: Send + AllocInner<T>, T: Sync> Sync for NodeData<A, T> {}
> +
> +/// Available MM node insertion modes
> +#[repr(u32)]
> +pub enum InsertMode {
> +    /// Search for the smallest hole (within the search range) that fits the desired node.
> +    ///
> +    /// Allocates the node from the bottom of the found hole.
> +    Best = bindings::drm_mm_insert_mode_DRM_MM_INSERT_BEST,
> +
> +    /// Search for the lowest hole (address closest to 0, within the search range) that fits the
> +    /// desired node.
> +    ///
> +    /// Allocates the node from the bottom of the found hole.
> +    Low = bindings::drm_mm_insert_mode_DRM_MM_INSERT_LOW,
> +
> +    /// Search for the highest hole (address closest to U64_MAX, within the search range) that fits
> +    /// the desired node.
> +    ///
> +    /// Allocates the node from the top of the found hole. The specified alignment for the node is
> +    /// applied to the base of the node (`Node.start()`).
> +    High = bindings::drm_mm_insert_mode_DRM_MM_INSERT_HIGH,
> +
> +    /// Search for the most recently evicted hole (within the search range) that fits the desired
> +    /// node. This is appropriate for use immediately after performing an eviction scan and removing
> +    /// the selected nodes to form a hole.
> +    ///
> +    /// Allocates the node from the bottom of the found hole.
> +    Evict = bindings::drm_mm_insert_mode_DRM_MM_INSERT_EVICT,
> +}
> +
> +/// A clonable, interlocked reference to the allocator state.
> +///
> +/// This is useful to perform actions on the user-supplied `AllocInner<T>` type given just a Node,
> +/// without immediately taking the lock.
> +#[derive(Clone)]
> +pub struct InnerRef<A: AllocInner<T>, T>(Arc<Mutex<MmInner<A, T>>>);
> +
> +impl<A: AllocInner<T>, T> InnerRef<A, T> {
> +    /// Operate on the user `AllocInner<T>` implementation, taking the lock.
> +    pub fn with<RetVal>(&self, cb: impl FnOnce(&mut A) -> RetVal) -> RetVal {
> +        let mut l = self.0.lock();
> +        cb(&mut l.1)
> +    }
> +}
> +
> +impl<A: AllocInner<T>, T> NodeData<A, T> {
> +    /// Returns the color of the node (an opaque value)
> +    pub fn color(&self) -> usize {
> +        self.node.color as usize
> +    }
> +
> +    /// Returns the start address of the node
> +    pub fn start(&self) -> u64 {
> +        self.node.start
> +    }
> +
> +    /// Returns the size of the node in bytes
> +    pub fn size(&self) -> u64 {
> +        self.node.size
> +    }
> +
> +    /// Operate on the user `AllocInner<T>` implementation associated with this node's allocator.
> +    pub fn with_inner<RetVal>(&self, cb: impl FnOnce(&mut A) -> RetVal) -> RetVal {
> +        let mut l = self.mm.lock();
> +        cb(&mut l.1)
> +    }
> +
> +    /// Return a clonable, detached reference to the allocator inner data.
> +    pub fn alloc_ref(&self) -> InnerRef<A, T> {
> +        InnerRef(self.mm.clone())
> +    }
> +
> +    /// Return a mutable reference to the inner data.
> +    pub fn inner_mut(self: Pin<&mut Self>) -> &mut T {
> +        // SAFETY: This is okay because inner is not structural
> +        unsafe { &mut self.get_unchecked_mut().inner }
> +    }
> +}
> +
> +impl<A: AllocInner<T>, T> Deref for NodeData<A, T> {
> +    type Target = T;
> +
> +    fn deref(&self) -> &Self::Target {
> +        &self.inner
> +    }
> +}
> +
> +impl<A: AllocInner<T>, T> Drop for NodeData<A, T> {
> +    fn drop(&mut self) {
> +        if self.valid {
> +            let mut guard = self.mm.lock();
> +
> +            // Inform the user allocator that a node is being dropped.
> +            guard
> +                .1
> +                .drop_object(self.start(), self.size(), self.color(), &mut self.inner);
> +            // SAFETY: The MM lock is still taken, so we can safely remove the node.
> +            unsafe { bindings::drm_mm_remove_node(&mut self.node) };
> +        }
> +    }
> +}
> +
> +/// An instance of a DRM MM range allocator.
> +pub struct Allocator<A: AllocInner<T>, T> {
> +    mm: Arc<Mutex<MmInner<A, T>>>,
> +    _p: PhantomData<T>,
> +}
> +
> +impl<A: AllocInner<T>, T> Allocator<A, T> {
> +    /// Create a new range allocator for the given start and size range of addresses.
> +    ///
> +    /// The user may optionally provide an inner object representing allocator state, which will
> +    /// be protected by the same lock. If not required, `()` can be used.
> +    pub fn new(
> +        start: u64,
> +        size: u64,
> +        inner: A,
> +        name: &'static CStr,
> +        lock_key: &'static LockClassKey,
> +    ) -> Result<Allocator<A, T>> {
> +        // SAFETY: We call `Mutex::init_lock` below.
> +        let mut mm: Pin<UniqueArc<Mutex<MmInner<A, T>>>> = UniqueArc::try_new(unsafe {
> +            Mutex::new(MmInner(Opaque::uninit(), inner, PhantomData))
> +        })?
> +        .into();
> +
> +        mm.as_mut().init_lock(name, lock_key);
> +
> +        unsafe {
> +            // SAFETY: The Opaque instance provides a valid pointer, and it is initialized after
> +            // this call.
> +            bindings::drm_mm_init(mm.lock().0.get(), start, size);
> +        }
> +
> +        Ok(Allocator {
> +            mm: mm.into(),
> +            _p: PhantomData,
> +        })
> +    }
> +
> +    /// Insert a new node into the allocator of a given size.
> +    ///
> +    /// `node` is the user `T` type data to store into the node.
> +    pub fn insert_node(&mut self, node: T, size: u64) -> Result<Node<A, T>> {
> +        self.insert_node_generic(node, size, 0, 0, InsertMode::Best)
> +    }
> +
> +    /// Insert a new node into the allocator of a given size, with configurable alignment,
> +    /// color, and insertion mode.
> +    ///
> +    /// `node` is the user `T` type data to store into the node.
> +    pub fn insert_node_generic(
> +        &mut self,
> +        node: T,
> +        size: u64,
> +        alignment: u64,
> +        color: usize,
> +        mode: InsertMode,
> +    ) -> Result<Node<A, T>> {
> +        self.insert_node_in_range(node, size, alignment, color, 0, u64::MAX, mode)
> +    }
> +
> +    /// Insert a new node into the allocator of a given size, with configurable alignment,
> +    /// color, insertion mode, and sub-range to allocate from.
> +    ///
> +    /// `node` is the user `T` type data to store into the node.
> +    #[allow(clippy::too_many_arguments)]
> +    pub fn insert_node_in_range(
> +        &mut self,
> +        node: T,
> +        size: u64,
> +        alignment: u64,
> +        color: usize,
> +        start: u64,
> +        end: u64,
> +        mode: InsertMode,
> +    ) -> Result<Node<A, T>> {
> +        let mut mm_node = Box::try_new(NodeData {
> +            // SAFETY: This C struct should be zero-initialized.
> +            node: unsafe { core::mem::zeroed() },
> +            valid: false,
> +            inner: node,
> +            mm: self.mm.clone(),
> +            _pin: PhantomPinned,
> +        })?;
> +
> +        let guard = self.mm.lock();
> +        // SAFETY: We hold the lock and all pointers are valid.
> +        to_result(unsafe {
> +            bindings::drm_mm_insert_node_in_range(
> +                guard.0.get(),
> +                &mut mm_node.node,
> +                size,
> +                alignment,
> +                color as core::ffi::c_ulong,
> +                start,
> +                end,
> +                mode as u32,
> +            )
> +        })?;
> +
> +        mm_node.valid = true;
> +
> +        Ok(Pin::from(mm_node))
> +    }
> +
> +    /// Insert a node into the allocator at a fixed start address.
> +    ///
> +    /// `node` is the user `T` type data to store into the node.
> +    pub fn reserve_node(
> +        &mut self,
> +        node: T,
> +        start: u64,
> +        size: u64,
> +        color: usize,
> +    ) -> Result<Node<A, T>> {
> +        let mut mm_node = Box::try_new(NodeData {
> +            // SAFETY: This C struct should be zero-initialized.
> +            node: unsafe { core::mem::zeroed() },
> +            valid: false,
> +            inner: node,
> +            mm: self.mm.clone(),
> +            _pin: PhantomPinned,
> +        })?;
> +
> +        mm_node.node.start = start;
> +        mm_node.node.size = size;
> +        mm_node.node.color = color as core::ffi::c_ulong;
> +
> +        let guard = self.mm.lock();
> +        // SAFETY: We hold the lock and all pointers are valid.
> +        to_result(unsafe { bindings::drm_mm_reserve_node(guard.0.get(), &mut mm_node.node) })?;
> +
> +        mm_node.valid = true;
> +
> +        Ok(Pin::from(mm_node))
> +    }
> +
> +    /// Operate on the inner user type `A`, taking the allocator lock
> +    pub fn with_inner<RetVal>(&self, cb: impl FnOnce(&mut A) -> RetVal) -> RetVal {
> +        let mut guard = self.mm.lock();
> +        cb(&mut guard.1)
> +    }
> +}
> +
> +impl<A: AllocInner<T>, T> Drop for MmInner<A, T> {
> +    fn drop(&mut self) {
> +        // SAFETY: If the MmInner is dropped then all nodes are gone (since they hold references),
> +        // so it is safe to tear down the allocator.
> +        unsafe {
> +            bindings::drm_mm_takedown(self.0.get());
> +        }
> +    }
> +}
> +
> +// MmInner is safely Send if the AllocInner user type is Send.
> +unsafe impl<A: Send + AllocInner<T>, T> Send for MmInner<A, T> {}
> diff --git a/rust/kernel/drm/mod.rs b/rust/kernel/drm/mod.rs
> index c44760a1332f..73fab2dee3af 100644
> --- a/rust/kernel/drm/mod.rs
> +++ b/rust/kernel/drm/mod.rs
> @@ -7,3 +7,4 @@ pub mod drv;
>  pub mod file;
>  pub mod gem;
>  pub mod ioctl;
> +pub mod mm;
> 
> -- 
> 2.35.1
>
  

On Thu, Apr 6, 2023 at 4:15 PM Daniel Vetter <daniel@ffwll.ch> wrote:
>
> Documentation:
>
> In drm we try to document all the interfaces that drivers use with formal
> docs. Yes there's some areas that are not great for historical reasons,
> but for new stuff and new wrappers we're really trying:
>
> - This helps in telling internal (even across .c files or in rust across
>   modules within a crate) from stuff drivers access. Sure you have static
>   in C or pub in rust, but that doesn't tell you whether it's public all
>   the way to drivers.

I think you may be talking about the value high-level docs here, but
just in case, visibility in Rust is flexible enough to expose (or not)
APIs to those that you need. In other words, it does tell you (and
enforces!) whether it is public all the way to drivers.

There is also the possibility of even more fancy visibility, but so
far we just needed `pub(crate)`.

`rustdoc` also shows/hides things as needed, thus the generated docs
for the crate should only show what is usable by others.

Then there is the `kernel` crate split, too.

> - ideally docs have a short intro section that explains the main concepts
>   and links to the main data structures and functions. Just to give
>   readers a good starting point to explore.

Agreed, this is typically done in Rust in the top-level doc comments
(module or crate). For the Rust side of the kernel, we are definitely
trying to emphasize the quality of the docs, including compile- and
runtime-tested examples.

Regarding linking, `rustdoc` already generates a listing with the
contents of each crate/module even if there is no other docs. So as
long as the short descriptions of the items are good, it may be fairly
readable already, e.g. see
https://rust-for-linux.github.io/docs/rust/kernel/sync/index.html for
an example in our old `rust` branch. But, of course, you can add extra
docs at that level too when there are many things or is unclear what
should be used.

Also note that, sometimes, the docs we write are in the type, rather
than the module, e.g. see the nice examples Wedson wrote for `RBTree`:
https://rust-for-linux.github.io/docs/rust/kernel/rbtree/struct.RBTree.html.

> - Linking all the things, so that readers can connect the different parts.
>   This is really important in C where e.g. get/put() or any such function
>   pairs all needed to be linked together. With rust I'm hoping that
>   rustdoc liberally sprinkles links already and we don't have to do this
>   as much.

If you mean within doc comments, it does! :) It is called "intra-doc
links". Basically, you just write something in-between square
brackets, and it is able to create the link to the right thing (in
most cases, otherwise you can help it more), e.g.

    /// Returns a new [`Foo`].

And, of course, for the rest of things that aren't inside comments, it
automatically provides links etc.

There has been work on `rustdoc` on getting "Jump to Definition" and
similar features to work on the source view, too.

> - Short explainers for parameters. For rust this also means type
>   parameters, for those even simplified examples of how drivers are
>   supposed to use them would help a lot in reading docs & understanding
>   concepts.

For parameters, we are not forcing to write explanations for every
parameter (as in providing a list), but rather writing what is
actually useful to know (referring to the parameters as needed). So it
depends on a case-by-case.

In any case, in general is clearer what parameters are compared to C,
due to the stronger typing. Of course, if one uses integers
everywhere, it is as confusing as C. But if one has a type, it is
easier to tell, plus one may jump with a click into the explanation of
that type etc.

Regarding examples, 100% agreed. And not only that, the examples are
enforced to be kept up to date by compiling and running them via KUnit
(not yet submitted for mainline, but we have been enforcing it for our
old `rust` branch for a long time).

> - Ideally links from the rust to the sphinx side to linke relevant
>   chapters together. Often the bigger explanations are in .rst files with
>   DOT graphs (kms has a bunch I've added) or similar, and it doesn't make
>   that much sense to duplicate all that on the rust side I guess. But it
>   needs to be discoverable.

Definitely. One next step is having easy-to-write links to the rST
docs. For this, a couple years ago I talked with the `rustdoc`
maintainers about having a "External references map file" feature, so
that we can link rST documents from the Rust docs, including generated
C docs too. For instance, ideally we would be able to use the square
brackets around a C type and have it work:

    /// Exposes the kernel’s [`struct wait_queue_head`] as a condition variable.

Regarding the bigger explanations: we are trying to keep most of the
docs close to the Rust code where it makes sense, as
module-level/crate-level docs, rather than as rST docs. This has
several benefits, like keeping them closer to the code, the linking
features, having them organized equally as the code, no need to know
whether there is a doc somewhere or not (e.g. if it is, it is near the
code), examples are compiled, etc.

Of course, sometimes longer-form docs and other documents may not make
sense as part of any code in particular, or may be shared across C and
Rust, etc., and there it may more sense to use `Documentation/` files
instead.

But, in general, the idea is that, compared to C, most of the docs go
into the code. To give an idea of the difference: so far, in our old
`rust` branch, we only needed a few documents in `Documentation/`
(e.g. the Quick Start guide etc.), and everything else went into the
code itself.

Cheers,
Miguel
  

On Thu, Apr 06, 2023 at 05:28:59PM +0200, Miguel Ojeda wrote:
> On Thu, Apr 6, 2023 at 4:15 PM Daniel Vetter <daniel@ffwll.ch> wrote:
> >
> > Documentation:
> >
> > In drm we try to document all the interfaces that drivers use with formal
> > docs. Yes there's some areas that are not great for historical reasons,
> > but for new stuff and new wrappers we're really trying:
> >
> > - This helps in telling internal (even across .c files or in rust across
> >   modules within a crate) from stuff drivers access. Sure you have static
> >   in C or pub in rust, but that doesn't tell you whether it's public all
> >   the way to drivers.
> 
> I think you may be talking about the value high-level docs here, but
> just in case, visibility in Rust is flexible enough to expose (or not)
> APIs to those that you need. In other words, it does tell you (and
> enforces!) whether it is public all the way to drivers.
> 
> There is also the possibility of even more fancy visibility, but so
> far we just needed `pub(crate)`.
> 
> `rustdoc` also shows/hides things as needed, thus the generated docs
> for the crate should only show what is usable by others.
> 
> Then there is the `kernel` crate split, too.
> 
> > - ideally docs have a short intro section that explains the main concepts
> >   and links to the main data structures and functions. Just to give
> >   readers a good starting point to explore.
> 
> Agreed, this is typically done in Rust in the top-level doc comments
> (module or crate). For the Rust side of the kernel, we are definitely
> trying to emphasize the quality of the docs, including compile- and
> runtime-tested examples.
> 
> Regarding linking, `rustdoc` already generates a listing with the
> contents of each crate/module even if there is no other docs. So as
> long as the short descriptions of the items are good, it may be fairly
> readable already, e.g. see
> https://rust-for-linux.github.io/docs/rust/kernel/sync/index.html for
> an example in our old `rust` branch. But, of course, you can add extra
> docs at that level too when there are many things or is unclear what
> should be used.
> 
> Also note that, sometimes, the docs we write are in the type, rather
> than the module, e.g. see the nice examples Wedson wrote for `RBTree`:
> https://rust-for-linux.github.io/docs/rust/kernel/rbtree/struct.RBTree.html.

Yeah this all looks great and very hyperlinked.

I think the only nit I have is that for types with two or more type
variables (like the rbtree) what each of them should represent in the top
intro. I can guess it's <Key, Value> and not the other way round, but
confirmation takes quite a bit of scrolling to check with the function
types.

Otherwise I think perfect api docs.

> > - Linking all the things, so that readers can connect the different parts.
> >   This is really important in C where e.g. get/put() or any such function
> >   pairs all needed to be linked together. With rust I'm hoping that
> >   rustdoc liberally sprinkles links already and we don't have to do this
> >   as much.
> 
> If you mean within doc comments, it does! :) It is called "intra-doc
> links". Basically, you just write something in-between square
> brackets, and it is able to create the link to the right thing (in
> most cases, otherwise you can help it more), e.g.
> 
>     /// Returns a new [`Foo`].
> 
> And, of course, for the rest of things that aren't inside comments, it
> automatically provides links etc.
> 
> There has been work on `rustdoc` on getting "Jump to Definition" and
> similar features to work on the source view, too.
> 
> > - Short explainers for parameters. For rust this also means type
> >   parameters, for those even simplified examples of how drivers are
> >   supposed to use them would help a lot in reading docs & understanding
> >   concepts.
> 
> For parameters, we are not forcing to write explanations for every
> parameter (as in providing a list), but rather writing what is
> actually useful to know (referring to the parameters as needed). So it
> depends on a case-by-case.
> 
> In any case, in general is clearer what parameters are compared to C,
> due to the stronger typing. Of course, if one uses integers
> everywhere, it is as confusing as C. But if one has a type, it is
> easier to tell, plus one may jump with a click into the explanation of
> that type etc.
> 
> Regarding examples, 100% agreed. And not only that, the examples are
> enforced to be kept up to date by compiling and running them via KUnit
> (not yet submitted for mainline, but we have been enforcing it for our
> old `rust` branch for a long time).
> 
> > - Ideally links from the rust to the sphinx side to linke relevant
> >   chapters together. Often the bigger explanations are in .rst files with
> >   DOT graphs (kms has a bunch I've added) or similar, and it doesn't make
> >   that much sense to duplicate all that on the rust side I guess. But it
> >   needs to be discoverable.
> 
> Definitely. One next step is having easy-to-write links to the rST
> docs. For this, a couple years ago I talked with the `rustdoc`
> maintainers about having a "External references map file" feature, so
> that we can link rST documents from the Rust docs, including generated
> C docs too. For instance, ideally we would be able to use the square
> brackets around a C type and have it work:
> 
>     /// Exposes the kernel’s [`struct wait_queue_head`] as a condition variable.
> 
> Regarding the bigger explanations: we are trying to keep most of the
> docs close to the Rust code where it makes sense, as
> module-level/crate-level docs, rather than as rST docs. This has
> several benefits, like keeping them closer to the code, the linking
> features, having them organized equally as the code, no need to know
> whether there is a doc somewhere or not (e.g. if it is, it is near the
> code), examples are compiled, etc.

Just a quick comment on this, that's the same we do on the C side. Most
overview chapters are actually DOC: sections pulled in from the code.

What I meant here is that for big overview stuff (like for modesetting how
the display pipe structures tie together as an example:
https://dri.freedesktop.org/docs/drm/gpu/drm-kms.html#overview)
it doesn't make sense to duplicate that in rustdoc once more.

> Of course, sometimes longer-form docs and other documents may not make
> sense as part of any code in particular, or may be shared across C and
> Rust, etc., and there it may more sense to use `Documentation/` files
> instead.
> 
> But, in general, the idea is that, compared to C, most of the docs go
> into the code. To give an idea of the difference: so far, in our old
> `rust` branch, we only needed a few documents in `Documentation/`
> (e.g. the Quick Start guide etc.), and everything else went into the
> code itself.

Maybe drm is the exception, but if you look at our .rst files we also have
most of our docs in the code:

https://cgit.freedesktop.org/drm/drm/tree/Documentation/gpu/drm-kms-helpers.rst

The rst files just provide the scaffolding because C dosn't have
crates/modules hierarchy that would do this for you automatically.

Cheers, Daniel
  

On 06/04/2023 23.15, Daniel Vetter wrote:
> On Tue, Mar 07, 2023 at 11:25:32PM +0900, Asahi Lina wrote:
>> drm_mm provides a simple range allocator, useful for managing virtual
>> address ranges. Add a Rust abstraction to expose this module to Rust
>> drivers.
>>
>> Signed-off-by: Asahi Lina <lina@asahilina.net>
> 
> In the cover letter you mentioned the design open about embedded the lock
> into the rust wrappers.
> 
> I think for a first step that's perfectly fine.
> 
> Longer term we might want to ramp up some "proof of locking"
> infrastructure in Rust, where callers can supply a lock guard and ideally
> rust validates at compile time that it's for the right type, and at
> runtime (like lockdep) that it's consistent and the callers don't mix up
> locks (like using different locks for the same drm_mm allocator).

That proof-of-lock tuff works in Rust too as far as I know.

But the general thread safety story in Rust is much simpler, you just 
use methods that take &mut self when locking is the caller's 
responsibility. That effectively implies that there can only be one 
reference that can call those methods at any given time, thanks to the 
borrow checker. Shared references only give you &self, a locked Mutex 
upgrades that to &mut self, and that's how you get proof of locking at 
compile time, through and through, not just for the type but for the 
specific object.

> There's a lot of libraries in the kernel that have this "caller ensures
> locking" pattern. drm/sched also has these requirements.

Yup, that all usually maps nicely to &mut self in Rust... except for the 
issue below.

> There's two other things I'd like to bring up on this patch though, just
> because it's a good example. But they're both really general points that
> apply for all the rust wrappers.
> 
> Documentation:
> 
> In drm we try to document all the interfaces that drivers use with formal
> docs. Yes there's some areas that are not great for historical reasons,
> but for new stuff and new wrappers we're really trying:
> 
> - This helps in telling internal (even across .c files or in rust across
>    modules within a crate) from stuff drivers access. Sure you have static
>    in C or pub in rust, but that doesn't tell you whether it's public all
>    the way to drivers.
> 
> - ideally docs have a short intro section that explains the main concepts
>    and links to the main data structures and functions. Just to give
>    readers a good starting point to explore.
> 
> - Linking all the things, so that readers can connect the different parts.
>    This is really important in C where e.g. get/put() or any such function
>    pairs all needed to be linked together. With rust I'm hoping that
>    rustdoc liberally sprinkles links already and we don't have to do this
>    as much.
> 
> - Short explainers for parameters. For rust this also means type
>    parameters, for those even simplified examples of how drivers are
>    supposed to use them would help a lot in reading docs & understanding
>    concepts.
> 
> - Ideally links from the rust to the sphinx side to linke relevant
>    chapters together. Often the bigger explanations are in .rst files with
>    DOT graphs (kms has a bunch I've added) or similar, and it doesn't make
>    that much sense to duplicate all that on the rust side I guess. But it
>    needs to be discoverable.
> 
> This might be more a discussion topic for the rust people than you
> directly. Still needed for the merge-ready patches eventually.

I don't know much about the doc gen stuff on the Rust side so yeah, this 
is something I need to look into to make it pretty and complete...

> Refcounting vs borrowing:
> 
> This is honestly much more the eyebrow raising one than the locking. Very
> often on the C side these datastructures all work with borrow semantics,
> and you need to explicitly upgrade to a full reference (kref_get or
> kref_get_unless_zero, depending whether it's a strong or weak reference)
> if you need the object outside of the mutex/lock guard section.
> 
> Again I think for now it's ok, but the sales pitch of rust is that it
> enables borrow lifetime checking with no runtime cost. Plus viz the vm
> cleanup example, if you have too many strong backreferences the cleanup
> flow gets complicated. And it would suck if rust drivers have to add
> complexity like the openrefcount for the vm example simply because we
> can't model the borrow semantics well enough to be safe.
> 
> So not something that's really bad here, but if we need to resort to full
> refcounting already for simple datastructures then I'm getting a bit
> worried about how well rust will cope with the really nasty borrowed
> reference tricks we're playing in other areas.
> 
> Again more a topic for the rust folks I think than specifically here about
> drm_mm wrapping. Just to get things going I think this is fine.

Yeeeeah... this is a *specific* problem. Drop.

The Allocator<T> itself is perfectly safe to implement without any 
locking, refcounting, or anything. You just make the methods take &mut 
self (as they already do), the caller can use it with a single reference 
or wrap it in an Arc<Mutex<T>> and share it, or whatever.

The problem is the Node<A, T>. When you Drop that, it has to go back to 
the Allocator. But now you're a different object, so no thread safety 
guarantees. And you need to keep the Allocator alive. So now to make a 
safe abstraction, you need refcounting and a mutex.

Lifetimes just don't work here, sadly. Not for a useful abstraction.

I'd love to hear from the other Rust folks whether they have any better 
ideas...

One thing that *can* be done is making the Drop illegal (Rust can't do 
this "natively" but Linux already has hacks for that, we can make it 
fail to link if the Drop is ever called). Then you'd have to actively 
return the Node to the Allocator with a free function. Since Drop is 
forbidden, and Node is pinned, you'd always have to either return Node 
objects to the Allocator or leak them. You could drop the Allocator 
before its nodes, but as far as I know drm_mm can safely handle that 
(though it will complain), and then due to the previous guarantees the 
*only* thing you could do with orphan nodes is leak their memory, which 
is safe.

It would work... but it breaks the whole Rust automagic Drop stuff.

Thinking about this a bit, I think I want the current mutex/arc 
semantics for something like a memory allocator (which is one of my 
primary use cases for drm_mm), since I definitely don't want to be 
manually returning objects to their allocator all over the place, nor 
have overarching lifetime requirements that the allocator outlive its 
objects for safety (that sounds like a can of worms I don't want to 
open, I'd much rather use a refcount even if I "think" I can prove the 
lifetime bounds ad-hoc). But for something like a drm_mm that is 
tracking VA ranges within a VM with all Nodes held internally, maybe I 
could manage it all internally and have all node destruction be handled 
via an explicit call into the Allocator.

Maybe the mm abstraction should offer both options? The extra locking 
can be implemented in terms of the base unlocked version I think 
(perhaps with some Deref abuse for ergonomics)... I definitely want to 
hear more opinions about this from other Rust folks, since there are 
probably other options I haven't considered...

Aside: This, and all the other DRM abstractions, were written before the 
pin_init stuff from y86 that is in review right now was ready. That may 
open up more interesting/ergonomic/efficient APIs for some cases, 
especially where Pin and embedding C types into user objects in some way 
are involved. So maybe there's room for improvement here. Just a sidenote.

> 
> Cheers, Daniel
> 
> 
>> ---
>>   rust/kernel/drm/mm.rs  | 309 +++++++++++++++++++++++++++++++++++++++++++++++++
>>   rust/kernel/drm/mod.rs |   1 +
>>   2 files changed, 310 insertions(+)
>>
>> diff --git a/rust/kernel/drm/mm.rs b/rust/kernel/drm/mm.rs
>> new file mode 100644
>> index 000000000000..83e27a7dcc7e
>> --- /dev/null
>> +++ b/rust/kernel/drm/mm.rs
>> @@ -0,0 +1,309 @@
>> +// SPDX-License-Identifier: GPL-2.0 OR MIT
>> +
>> +//! DRM MM range allocator
>> +//!
>> +//! C header: [`include/linux/drm/drm_mm.h`](../../../../include/linux/drm/drm_mm.h)
>> +
>> +use crate::{
>> +    bindings,
>> +    error::{to_result, Result},
>> +    str::CStr,
>> +    sync::{Arc, LockClassKey, LockIniter, Mutex, UniqueArc},
>> +    types::Opaque,
>> +};
>> +
>> +use alloc::boxed::Box;
>> +
>> +use core::{
>> +    marker::{PhantomData, PhantomPinned},
>> +    ops::Deref,
>> +    pin::Pin,
>> +};
>> +
>> +/// Type alias representing a DRM MM node.
>> +pub type Node<A, T> = Pin<Box<NodeData<A, T>>>;
>> +
>> +/// Trait which must be implemented by the inner allocator state type provided by the user.
>> +pub trait AllocInner<T> {
>> +    /// Notification that a node was dropped from the allocator.
>> +    fn drop_object(&mut self, _start: u64, _size: u64, _color: usize, _object: &mut T) {}
>> +}
>> +
>> +impl<T> AllocInner<T> for () {}
>> +
>> +/// Wrapper type for a `struct drm_mm` plus user AllocInner object.
>> +///
>> +/// # Invariants
>> +/// The `drm_mm` struct is valid and initialized.
>> +struct MmInner<A: AllocInner<T>, T>(Opaque<bindings::drm_mm>, A, PhantomData<T>);
>> +
>> +/// Represents a single allocated node in the MM allocator
>> +pub struct NodeData<A: AllocInner<T>, T> {
>> +    node: bindings::drm_mm_node,
>> +    mm: Arc<Mutex<MmInner<A, T>>>,
>> +    valid: bool,
>> +    /// A drm_mm_node needs to be pinned because nodes reference each other in a linked list.
>> +    _pin: PhantomPinned,
>> +    inner: T,
>> +}
>> +
>> +// SAFETY: Allocator ops take the mutex, and there are no mutable actions on the node.
>> +unsafe impl<A: Send + AllocInner<T>, T: Send> Send for NodeData<A, T> {}
>> +unsafe impl<A: Send + AllocInner<T>, T: Sync> Sync for NodeData<A, T> {}
>> +
>> +/// Available MM node insertion modes
>> +#[repr(u32)]
>> +pub enum InsertMode {
>> +    /// Search for the smallest hole (within the search range) that fits the desired node.
>> +    ///
>> +    /// Allocates the node from the bottom of the found hole.
>> +    Best = bindings::drm_mm_insert_mode_DRM_MM_INSERT_BEST,
>> +
>> +    /// Search for the lowest hole (address closest to 0, within the search range) that fits the
>> +    /// desired node.
>> +    ///
>> +    /// Allocates the node from the bottom of the found hole.
>> +    Low = bindings::drm_mm_insert_mode_DRM_MM_INSERT_LOW,
>> +
>> +    /// Search for the highest hole (address closest to U64_MAX, within the search range) that fits
>> +    /// the desired node.
>> +    ///
>> +    /// Allocates the node from the top of the found hole. The specified alignment for the node is
>> +    /// applied to the base of the node (`Node.start()`).
>> +    High = bindings::drm_mm_insert_mode_DRM_MM_INSERT_HIGH,
>> +
>> +    /// Search for the most recently evicted hole (within the search range) that fits the desired
>> +    /// node. This is appropriate for use immediately after performing an eviction scan and removing
>> +    /// the selected nodes to form a hole.
>> +    ///
>> +    /// Allocates the node from the bottom of the found hole.
>> +    Evict = bindings::drm_mm_insert_mode_DRM_MM_INSERT_EVICT,
>> +}
>> +
>> +/// A clonable, interlocked reference to the allocator state.
>> +///
>> +/// This is useful to perform actions on the user-supplied `AllocInner<T>` type given just a Node,
>> +/// without immediately taking the lock.
>> +#[derive(Clone)]
>> +pub struct InnerRef<A: AllocInner<T>, T>(Arc<Mutex<MmInner<A, T>>>);
>> +
>> +impl<A: AllocInner<T>, T> InnerRef<A, T> {
>> +    /// Operate on the user `AllocInner<T>` implementation, taking the lock.
>> +    pub fn with<RetVal>(&self, cb: impl FnOnce(&mut A) -> RetVal) -> RetVal {
>> +        let mut l = self.0.lock();
>> +        cb(&mut l.1)
>> +    }
>> +}
>> +
>> +impl<A: AllocInner<T>, T> NodeData<A, T> {
>> +    /// Returns the color of the node (an opaque value)
>> +    pub fn color(&self) -> usize {
>> +        self.node.color as usize
>> +    }
>> +
>> +    /// Returns the start address of the node
>> +    pub fn start(&self) -> u64 {
>> +        self.node.start
>> +    }
>> +
>> +    /// Returns the size of the node in bytes
>> +    pub fn size(&self) -> u64 {
>> +        self.node.size
>> +    }
>> +
>> +    /// Operate on the user `AllocInner<T>` implementation associated with this node's allocator.
>> +    pub fn with_inner<RetVal>(&self, cb: impl FnOnce(&mut A) -> RetVal) -> RetVal {
>> +        let mut l = self.mm.lock();
>> +        cb(&mut l.1)
>> +    }
>> +
>> +    /// Return a clonable, detached reference to the allocator inner data.
>> +    pub fn alloc_ref(&self) -> InnerRef<A, T> {
>> +        InnerRef(self.mm.clone())
>> +    }
>> +
>> +    /// Return a mutable reference to the inner data.
>> +    pub fn inner_mut(self: Pin<&mut Self>) -> &mut T {
>> +        // SAFETY: This is okay because inner is not structural
>> +        unsafe { &mut self.get_unchecked_mut().inner }
>> +    }
>> +}
>> +
>> +impl<A: AllocInner<T>, T> Deref for NodeData<A, T> {
>> +    type Target = T;
>> +
>> +    fn deref(&self) -> &Self::Target {
>> +        &self.inner
>> +    }
>> +}
>> +
>> +impl<A: AllocInner<T>, T> Drop for NodeData<A, T> {
>> +    fn drop(&mut self) {
>> +        if self.valid {
>> +            let mut guard = self.mm.lock();
>> +
>> +            // Inform the user allocator that a node is being dropped.
>> +            guard
>> +                .1
>> +                .drop_object(self.start(), self.size(), self.color(), &mut self.inner);
>> +            // SAFETY: The MM lock is still taken, so we can safely remove the node.
>> +            unsafe { bindings::drm_mm_remove_node(&mut self.node) };
>> +        }
>> +    }
>> +}
>> +
>> +/// An instance of a DRM MM range allocator.
>> +pub struct Allocator<A: AllocInner<T>, T> {
>> +    mm: Arc<Mutex<MmInner<A, T>>>,
>> +    _p: PhantomData<T>,
>> +}
>> +
>> +impl<A: AllocInner<T>, T> Allocator<A, T> {
>> +    /// Create a new range allocator for the given start and size range of addresses.
>> +    ///
>> +    /// The user may optionally provide an inner object representing allocator state, which will
>> +    /// be protected by the same lock. If not required, `()` can be used.
>> +    pub fn new(
>> +        start: u64,
>> +        size: u64,
>> +        inner: A,
>> +        name: &'static CStr,
>> +        lock_key: &'static LockClassKey,
>> +    ) -> Result<Allocator<A, T>> {
>> +        // SAFETY: We call `Mutex::init_lock` below.
>> +        let mut mm: Pin<UniqueArc<Mutex<MmInner<A, T>>>> = UniqueArc::try_new(unsafe {
>> +            Mutex::new(MmInner(Opaque::uninit(), inner, PhantomData))
>> +        })?
>> +        .into();
>> +
>> +        mm.as_mut().init_lock(name, lock_key);
>> +
>> +        unsafe {
>> +            // SAFETY: The Opaque instance provides a valid pointer, and it is initialized after
>> +            // this call.
>> +            bindings::drm_mm_init(mm.lock().0.get(), start, size);
>> +        }
>> +
>> +        Ok(Allocator {
>> +            mm: mm.into(),
>> +            _p: PhantomData,
>> +        })
>> +    }
>> +
>> +    /// Insert a new node into the allocator of a given size.
>> +    ///
>> +    /// `node` is the user `T` type data to store into the node.
>> +    pub fn insert_node(&mut self, node: T, size: u64) -> Result<Node<A, T>> {
>> +        self.insert_node_generic(node, size, 0, 0, InsertMode::Best)
>> +    }
>> +
>> +    /// Insert a new node into the allocator of a given size, with configurable alignment,
>> +    /// color, and insertion mode.
>> +    ///
>> +    /// `node` is the user `T` type data to store into the node.
>> +    pub fn insert_node_generic(
>> +        &mut self,
>> +        node: T,
>> +        size: u64,
>> +        alignment: u64,
>> +        color: usize,
>> +        mode: InsertMode,
>> +    ) -> Result<Node<A, T>> {
>> +        self.insert_node_in_range(node, size, alignment, color, 0, u64::MAX, mode)
>> +    }
>> +
>> +    /// Insert a new node into the allocator of a given size, with configurable alignment,
>> +    /// color, insertion mode, and sub-range to allocate from.
>> +    ///
>> +    /// `node` is the user `T` type data to store into the node.
>> +    #[allow(clippy::too_many_arguments)]
>> +    pub fn insert_node_in_range(
>> +        &mut self,
>> +        node: T,
>> +        size: u64,
>> +        alignment: u64,
>> +        color: usize,
>> +        start: u64,
>> +        end: u64,
>> +        mode: InsertMode,
>> +    ) -> Result<Node<A, T>> {
>> +        let mut mm_node = Box::try_new(NodeData {
>> +            // SAFETY: This C struct should be zero-initialized.
>> +            node: unsafe { core::mem::zeroed() },
>> +            valid: false,
>> +            inner: node,
>> +            mm: self.mm.clone(),
>> +            _pin: PhantomPinned,
>> +        })?;
>> +
>> +        let guard = self.mm.lock();
>> +        // SAFETY: We hold the lock and all pointers are valid.
>> +        to_result(unsafe {
>> +            bindings::drm_mm_insert_node_in_range(
>> +                guard.0.get(),
>> +                &mut mm_node.node,
>> +                size,
>> +                alignment,
>> +                color as core::ffi::c_ulong,
>> +                start,
>> +                end,
>> +                mode as u32,
>> +            )
>> +        })?;
>> +
>> +        mm_node.valid = true;
>> +
>> +        Ok(Pin::from(mm_node))
>> +    }
>> +
>> +    /// Insert a node into the allocator at a fixed start address.
>> +    ///
>> +    /// `node` is the user `T` type data to store into the node.
>> +    pub fn reserve_node(
>> +        &mut self,
>> +        node: T,
>> +        start: u64,
>> +        size: u64,
>> +        color: usize,
>> +    ) -> Result<Node<A, T>> {
>> +        let mut mm_node = Box::try_new(NodeData {
>> +            // SAFETY: This C struct should be zero-initialized.
>> +            node: unsafe { core::mem::zeroed() },
>> +            valid: false,
>> +            inner: node,
>> +            mm: self.mm.clone(),
>> +            _pin: PhantomPinned,
>> +        })?;
>> +
>> +        mm_node.node.start = start;
>> +        mm_node.node.size = size;
>> +        mm_node.node.color = color as core::ffi::c_ulong;
>> +
>> +        let guard = self.mm.lock();
>> +        // SAFETY: We hold the lock and all pointers are valid.
>> +        to_result(unsafe { bindings::drm_mm_reserve_node(guard.0.get(), &mut mm_node.node) })?;
>> +
>> +        mm_node.valid = true;
>> +
>> +        Ok(Pin::from(mm_node))
>> +    }
>> +
>> +    /// Operate on the inner user type `A`, taking the allocator lock
>> +    pub fn with_inner<RetVal>(&self, cb: impl FnOnce(&mut A) -> RetVal) -> RetVal {
>> +        let mut guard = self.mm.lock();
>> +        cb(&mut guard.1)
>> +    }
>> +}
>> +
>> +impl<A: AllocInner<T>, T> Drop for MmInner<A, T> {
>> +    fn drop(&mut self) {
>> +        // SAFETY: If the MmInner is dropped then all nodes are gone (since they hold references),
>> +        // so it is safe to tear down the allocator.
>> +        unsafe {
>> +            bindings::drm_mm_takedown(self.0.get());
>> +        }
>> +    }
>> +}
>> +
>> +// MmInner is safely Send if the AllocInner user type is Send.
>> +unsafe impl<A: Send + AllocInner<T>, T> Send for MmInner<A, T> {}
>> diff --git a/rust/kernel/drm/mod.rs b/rust/kernel/drm/mod.rs
>> index c44760a1332f..73fab2dee3af 100644
>> --- a/rust/kernel/drm/mod.rs
>> +++ b/rust/kernel/drm/mod.rs
>> @@ -7,3 +7,4 @@ pub mod drv;
>>   pub mod file;
>>   pub mod gem;
>>   pub mod ioctl;
>> +pub mod mm;
>>
>> -- 
>> 2.35.1
>>
> 

~~ Lina
  

On Fri, Apr 07, 2023 at 12:53:47AM +0900, Asahi Lina wrote:
> On 06/04/2023 23.15, Daniel Vetter wrote:
> > On Tue, Mar 07, 2023 at 11:25:32PM +0900, Asahi Lina wrote:
> > > drm_mm provides a simple range allocator, useful for managing virtual
> > > address ranges. Add a Rust abstraction to expose this module to Rust
> > > drivers.
> > > 
> > > Signed-off-by: Asahi Lina <lina@asahilina.net>
> > 
> > In the cover letter you mentioned the design open about embedded the lock
> > into the rust wrappers.
> > 
> > I think for a first step that's perfectly fine.
> > 
> > Longer term we might want to ramp up some "proof of locking"
> > infrastructure in Rust, where callers can supply a lock guard and ideally
> > rust validates at compile time that it's for the right type, and at
> > runtime (like lockdep) that it's consistent and the callers don't mix up
> > locks (like using different locks for the same drm_mm allocator).
> 
> That proof-of-lock tuff works in Rust too as far as I know.
> 
> But the general thread safety story in Rust is much simpler, you just use
> methods that take &mut self when locking is the caller's responsibility.
> That effectively implies that there can only be one reference that can call
> those methods at any given time, thanks to the borrow checker. Shared
> references only give you &self, a locked Mutex upgrades that to &mut self,
> and that's how you get proof of locking at compile time, through and
> through, not just for the type but for the specific object.

Hm that still has the problem of making sure that you supply the right
lock (for generic abstractions like drm_mm or drm/sched where the lock is
supplied by the driver.

Once we have the lock then yeah borrow checker makes sure you can't screw
up, worst case needs a PhantomData (I guess) as toke of proof to pass
around the borrowed lifetime (If I got that right from your use of
PhantomData in the sched wrappers).

> > There's a lot of libraries in the kernel that have this "caller ensures
> > locking" pattern. drm/sched also has these requirements.
> 
> Yup, that all usually maps nicely to &mut self in Rust... except for the
> issue below.
> 
> > There's two other things I'd like to bring up on this patch though, just
> > because it's a good example. But they're both really general points that
> > apply for all the rust wrappers.
> > 
> > Documentation:
> > 
> > In drm we try to document all the interfaces that drivers use with formal
> > docs. Yes there's some areas that are not great for historical reasons,
> > but for new stuff and new wrappers we're really trying:
> > 
> > - This helps in telling internal (even across .c files or in rust across
> >    modules within a crate) from stuff drivers access. Sure you have static
> >    in C or pub in rust, but that doesn't tell you whether it's public all
> >    the way to drivers.
> > 
> > - ideally docs have a short intro section that explains the main concepts
> >    and links to the main data structures and functions. Just to give
> >    readers a good starting point to explore.
> > 
> > - Linking all the things, so that readers can connect the different parts.
> >    This is really important in C where e.g. get/put() or any such function
> >    pairs all needed to be linked together. With rust I'm hoping that
> >    rustdoc liberally sprinkles links already and we don't have to do this
> >    as much.
> > 
> > - Short explainers for parameters. For rust this also means type
> >    parameters, for those even simplified examples of how drivers are
> >    supposed to use them would help a lot in reading docs & understanding
> >    concepts.
> > 
> > - Ideally links from the rust to the sphinx side to linke relevant
> >    chapters together. Often the bigger explanations are in .rst files with
> >    DOT graphs (kms has a bunch I've added) or similar, and it doesn't make
> >    that much sense to duplicate all that on the rust side I guess. But it
> >    needs to be discoverable.
> > 
> > This might be more a discussion topic for the rust people than you
> > directly. Still needed for the merge-ready patches eventually.
> 
> I don't know much about the doc gen stuff on the Rust side so yeah, this is
> something I need to look into to make it pretty and complete...

From what Miguel has shown I think it's all there already, and the only
missing pieces are the cross-linking at a chapter level from rustdoc to
rst and sphinx to rstdoc too ideally. But I think for most rust wrappers
that will be one link each direction only (e.g. C drm_mm linking to
kernel::drm::MM and other way round and done). So absolutely no problem if
that one item is sorted out post merge once rustdoc/kernel-sphinx are
ready.

> > Refcounting vs borrowing:
> > 
> > This is honestly much more the eyebrow raising one than the locking. Very
> > often on the C side these datastructures all work with borrow semantics,
> > and you need to explicitly upgrade to a full reference (kref_get or
> > kref_get_unless_zero, depending whether it's a strong or weak reference)
> > if you need the object outside of the mutex/lock guard section.
> > 
> > Again I think for now it's ok, but the sales pitch of rust is that it
> > enables borrow lifetime checking with no runtime cost. Plus viz the vm
> > cleanup example, if you have too many strong backreferences the cleanup
> > flow gets complicated. And it would suck if rust drivers have to add
> > complexity like the openrefcount for the vm example simply because we
> > can't model the borrow semantics well enough to be safe.
> > 
> > So not something that's really bad here, but if we need to resort to full
> > refcounting already for simple datastructures then I'm getting a bit
> > worried about how well rust will cope with the really nasty borrowed
> > reference tricks we're playing in other areas.
> > 
> > Again more a topic for the rust folks I think than specifically here about
> > drm_mm wrapping. Just to get things going I think this is fine.
> 
> Yeeeeah... this is a *specific* problem. Drop.
> 
> The Allocator<T> itself is perfectly safe to implement without any locking,
> refcounting, or anything. You just make the methods take &mut self (as they
> already do), the caller can use it with a single reference or wrap it in an
> Arc<Mutex<T>> and share it, or whatever.
> 
> The problem is the Node<A, T>. When you Drop that, it has to go back to the
> Allocator. But now you're a different object, so no thread safety
> guarantees. And you need to keep the Allocator alive. So now to make a safe
> abstraction, you need refcounting and a mutex.
> 
> Lifetimes just don't work here, sadly. Not for a useful abstraction.
> 
> I'd love to hear from the other Rust folks whether they have any better
> ideas...

Hm yeah I think I get the gist of the issue. At time of Drop there's no
allocator reference you can borrow and so you're screwed.

In C we tend to solve that by passing both to the unlink/drop stuff (and
rust could then ensure that we have legit borrows for both), but I guess
that just totally wreaks entire wrapper and makes it really rough to use.

> One thing that *can* be done is making the Drop illegal (Rust can't do this
> "natively" but Linux already has hacks for that, we can make it fail to link
> if the Drop is ever called). Then you'd have to actively return the Node to
> the Allocator with a free function. Since Drop is forbidden, and Node is
> pinned, you'd always have to either return Node objects to the Allocator or
> leak them. You could drop the Allocator before its nodes, but as far as I
> know drm_mm can safely handle that (though it will complain), and then due
> to the previous guarantees the *only* thing you could do with orphan nodes
> is leak their memory, which is safe.
> 
> It would work... but it breaks the whole Rust automagic Drop stuff.

Yeah I think I see the challenge ...

> Thinking about this a bit, I think I want the current mutex/arc semantics
> for something like a memory allocator (which is one of my primary use cases
> for drm_mm), since I definitely don't want to be manually returning objects
> to their allocator all over the place, nor have overarching lifetime
> requirements that the allocator outlive its objects for safety (that sounds
> like a can of worms I don't want to open, I'd much rather use a refcount
> even if I "think" I can prove the lifetime bounds ad-hoc). But for something
> like a drm_mm that is tracking VA ranges within a VM with all Nodes held
> internally, maybe I could manage it all internally and have all node
> destruction be handled via an explicit call into the Allocator.

Yeah I think for gpuva we need to do better, but assuming the gpuva
library is in C then rust would just need to encode the safety properties
that (hopefully) the C library guarantees ...

And for any driver that just wants to use some range manager the standard
wrapping leans heavily on the side of "easy to use".

> Maybe the mm abstraction should offer both options? The extra locking can be
> implemented in terms of the base unlocked version I think (perhaps with some
> Deref abuse for ergonomics)... I definitely want to hear more opinions about
> this from other Rust folks, since there are probably other options I haven't
> considered...

I don't think we need the more raw/tricky one, at least not until we have
some serious libraries like gpuva implemented in rust. Or drivers
reimplementing the gpuva stuff in their driver :-)

> Aside: This, and all the other DRM abstractions, were written before the
> pin_init stuff from y86 that is in review right now was ready. That may open
> up more interesting/ergonomic/efficient APIs for some cases, especially
> where Pin and embedding C types into user objects in some way are involved.
> So maybe there's room for improvement here. Just a sidenote.

Ah good to know, and yeah that make open some interesting options.
-Daniel
  

On 07/04/2023 01.13, Daniel Vetter wrote:
> On Fri, Apr 07, 2023 at 12:53:47AM +0900, Asahi Lina wrote:
>> On 06/04/2023 23.15, Daniel Vetter wrote:
>>> On Tue, Mar 07, 2023 at 11:25:32PM +0900, Asahi Lina wrote:
>>>> drm_mm provides a simple range allocator, useful for managing virtual
>>>> address ranges. Add a Rust abstraction to expose this module to Rust
>>>> drivers.
>>>>
>>>> Signed-off-by: Asahi Lina <lina@asahilina.net>
>>>
>>> In the cover letter you mentioned the design open about embedded the lock
>>> into the rust wrappers.
>>>
>>> I think for a first step that's perfectly fine.
>>>
>>> Longer term we might want to ramp up some "proof of locking"
>>> infrastructure in Rust, where callers can supply a lock guard and ideally
>>> rust validates at compile time that it's for the right type, and at
>>> runtime (like lockdep) that it's consistent and the callers don't mix up
>>> locks (like using different locks for the same drm_mm allocator).
>>
>> That proof-of-lock tuff works in Rust too as far as I know.
>>
>> But the general thread safety story in Rust is much simpler, you just use
>> methods that take &mut self when locking is the caller's responsibility.
>> That effectively implies that there can only be one reference that can call
>> those methods at any given time, thanks to the borrow checker. Shared
>> references only give you &self, a locked Mutex upgrades that to &mut self,
>> and that's how you get proof of locking at compile time, through and
>> through, not just for the type but for the specific object.
> 
> Hm that still has the problem of making sure that you supply the right
> lock (for generic abstractions like drm_mm or drm/sched where the lock is
> supplied by the driver.

No no, I mean you don't have to supply the lock at all. The idea is that 
if you have a mutable reference to the object *at all* then Rust says 
that's effectively interlocked, whether you achieve that with an actual 
lock or just by not sharing the object to begin with.

This is the standard pattern in Rust. Thread-safe methods take &self, 
and you can call those from multiple threads at once. Thread-unsafe 
methods take &mut self, and you can only call them from one thread at 
once. Mutex is one mechanism that allows you to upgrade a shared &self 
to a &mut self (while holding the lock). The actual object doesn't know 
anything about mutexes or locking, it just relies on the more 
fundamental property that Rust says that if you have a &mut obj, 
absolutely nobody else does, at any given time, by definition.

(And then everything also needs to impl Send + Sync for this to work 
across threads, but that's usually what you want)

Basically if there were to exist a Rust abstraction/object/anything that 
allows two threads to get ahold of a &mut to the same object at the same 
time without using unsafe, that abstraction/etc would be broken and 
unsound (and necessarily have to involve bad unsafe code within, because 
you can't do that with just safe code, the borrow checker stops you), 
and the state of affairs of two threads having such a reference is 
outright undefined behavior in the language model.

> Once we have the lock then yeah borrow checker makes sure you can't screw
> up, worst case needs a PhantomData (I guess) as toke of proof to pass
> around the borrowed lifetime (If I got that right from your use of
> PhantomData in the sched wrappers).

Ah, PhantomData is just a hack because Rust wants you to use all type 
parameters inside structs even when you don't actually need them for 
anything because they only have meaning to the abstraction itself. 
Without it it won't compile. Something something deep type system black 
magic rules (I'm pretty sure this requirement isn't gratuitous but I 
don't know what the whole story is here).

The lock does give you a Guard you could pass somewhere as proof, which 
itself contains a lifetime that ties it to the Mutex, but more 
importantly that Guard implements DerefMut to give you a &mut to 
whatever is inside the Mutex, and *that* mutable reference is the proof 
that you are the sole execution context with the right to access that 
one particular object. At that point the Guard doesn't matter, and 
lifetimes tie everything together so you can't stash that &mut somewhere 
else or anything like that to break the rules (modulo unsafe code, of 
course!).

> 
>>> There's a lot of libraries in the kernel that have this "caller ensures
>>> locking" pattern. drm/sched also has these requirements.
>>
>> Yup, that all usually maps nicely to &mut self in Rust... except for the
>> issue below.
>>
>>> There's two other things I'd like to bring up on this patch though, just
>>> because it's a good example. But they're both really general points that
>>> apply for all the rust wrappers.
>>>
>>> Documentation:
>>>
>>> In drm we try to document all the interfaces that drivers use with formal
>>> docs. Yes there's some areas that are not great for historical reasons,
>>> but for new stuff and new wrappers we're really trying:
>>>
>>> - This helps in telling internal (even across .c files or in rust across
>>>     modules within a crate) from stuff drivers access. Sure you have static
>>>     in C or pub in rust, but that doesn't tell you whether it's public all
>>>     the way to drivers.
>>>
>>> - ideally docs have a short intro section that explains the main concepts
>>>     and links to the main data structures and functions. Just to give
>>>     readers a good starting point to explore.
>>>
>>> - Linking all the things, so that readers can connect the different parts.
>>>     This is really important in C where e.g. get/put() or any such function
>>>     pairs all needed to be linked together. With rust I'm hoping that
>>>     rustdoc liberally sprinkles links already and we don't have to do this
>>>     as much.
>>>
>>> - Short explainers for parameters. For rust this also means type
>>>     parameters, for those even simplified examples of how drivers are
>>>     supposed to use them would help a lot in reading docs & understanding
>>>     concepts.
>>>
>>> - Ideally links from the rust to the sphinx side to linke relevant
>>>     chapters together. Often the bigger explanations are in .rst files with
>>>     DOT graphs (kms has a bunch I've added) or similar, and it doesn't make
>>>     that much sense to duplicate all that on the rust side I guess. But it
>>>     needs to be discoverable.
>>>
>>> This might be more a discussion topic for the rust people than you
>>> directly. Still needed for the merge-ready patches eventually.
>>
>> I don't know much about the doc gen stuff on the Rust side so yeah, this is
>> something I need to look into to make it pretty and complete...
> 
>  From what Miguel has shown I think it's all there already, and the only
> missing pieces are the cross-linking at a chapter level from rustdoc to
> rst and sphinx to rstdoc too ideally. But I think for most rust wrappers
> that will be one link each direction only (e.g. C drm_mm linking to
> kernel::drm::MM and other way round and done). So absolutely no problem if
> that one item is sorted out post merge once rustdoc/kernel-sphinx are
> ready.
> 
>>> Refcounting vs borrowing:
>>>
>>> This is honestly much more the eyebrow raising one than the locking. Very
>>> often on the C side these datastructures all work with borrow semantics,
>>> and you need to explicitly upgrade to a full reference (kref_get or
>>> kref_get_unless_zero, depending whether it's a strong or weak reference)
>>> if you need the object outside of the mutex/lock guard section.
>>>
>>> Again I think for now it's ok, but the sales pitch of rust is that it
>>> enables borrow lifetime checking with no runtime cost. Plus viz the vm
>>> cleanup example, if you have too many strong backreferences the cleanup
>>> flow gets complicated. And it would suck if rust drivers have to add
>>> complexity like the openrefcount for the vm example simply because we
>>> can't model the borrow semantics well enough to be safe.
>>>
>>> So not something that's really bad here, but if we need to resort to full
>>> refcounting already for simple datastructures then I'm getting a bit
>>> worried about how well rust will cope with the really nasty borrowed
>>> reference tricks we're playing in other areas.
>>>
>>> Again more a topic for the rust folks I think than specifically here about
>>> drm_mm wrapping. Just to get things going I think this is fine.
>>
>> Yeeeeah... this is a *specific* problem. Drop.
>>
>> The Allocator<T> itself is perfectly safe to implement without any locking,
>> refcounting, or anything. You just make the methods take &mut self (as they
>> already do), the caller can use it with a single reference or wrap it in an
>> Arc<Mutex<T>> and share it, or whatever.
>>
>> The problem is the Node<A, T>. When you Drop that, it has to go back to the
>> Allocator. But now you're a different object, so no thread safety
>> guarantees. And you need to keep the Allocator alive. So now to make a safe
>> abstraction, you need refcounting and a mutex.
>>
>> Lifetimes just don't work here, sadly. Not for a useful abstraction.
>>
>> I'd love to hear from the other Rust folks whether they have any better
>> ideas...
> 
> Hm yeah I think I get the gist of the issue. At time of Drop there's no
> allocator reference you can borrow and so you're screwed.
> 
> In C we tend to solve that by passing both to the unlink/drop stuff (and
> rust could then ensure that we have legit borrows for both), but I guess
> that just totally wreaks entire wrapper and makes it really rough to use.

Yup, that's the issue ^^;;

> 
>> One thing that *can* be done is making the Drop illegal (Rust can't do this
>> "natively" but Linux already has hacks for that, we can make it fail to link
>> if the Drop is ever called). Then you'd have to actively return the Node to
>> the Allocator with a free function. Since Drop is forbidden, and Node is
>> pinned, you'd always have to either return Node objects to the Allocator or
>> leak them. You could drop the Allocator before its nodes, but as far as I
>> know drm_mm can safely handle that (though it will complain), and then due
>> to the previous guarantees the *only* thing you could do with orphan nodes
>> is leak their memory, which is safe.
>>
>> It would work... but it breaks the whole Rust automagic Drop stuff.
> 
> Yeah I think I see the challenge ...
> 
>> Thinking about this a bit, I think I want the current mutex/arc semantics
>> for something like a memory allocator (which is one of my primary use cases
>> for drm_mm), since I definitely don't want to be manually returning objects
>> to their allocator all over the place, nor have overarching lifetime
>> requirements that the allocator outlive its objects for safety (that sounds
>> like a can of worms I don't want to open, I'd much rather use a refcount
>> even if I "think" I can prove the lifetime bounds ad-hoc). But for something
>> like a drm_mm that is tracking VA ranges within a VM with all Nodes held
>> internally, maybe I could manage it all internally and have all node
>> destruction be handled via an explicit call into the Allocator.
> 
> Yeah I think for gpuva we need to do better, but assuming the gpuva
> library is in C then rust would just need to encode the safety properties
> that (hopefully) the C library guarantees ...

Yeah, if this is going to be common C code using drm_mm then it can 
provide whatever safety properties it wants and use drm_mm in ways not 
possible with the Rust abstraction, of course.

> And for any driver that just wants to use some range manager the standard
> wrapping leans heavily on the side of "easy to use".
> 
>> Maybe the mm abstraction should offer both options? The extra locking can be
>> implemented in terms of the base unlocked version I think (perhaps with some
>> Deref abuse for ergonomics)... I definitely want to hear more opinions about
>> this from other Rust folks, since there are probably other options I haven't
>> considered...
> 
> I don't think we need the more raw/tricky one, at least not until we have
> some serious libraries like gpuva implemented in rust. Or drivers
> reimplementing the gpuva stuff in their driver :-)

It only just hit me that gpuva is an actual thing that's in RFC. Sounds 
like I should give it a shot when I do the vm_bind stuff instead of 
reinventing that wheel (which was my original plan)... sorry if I've 
been a bit slow here.

>> Aside: This, and all the other DRM abstractions, were written before the
>> pin_init stuff from y86 that is in review right now was ready. That may open
>> up more interesting/ergonomic/efficient APIs for some cases, especially
>> where Pin and embedding C types into user objects in some way are involved.
>> So maybe there's room for improvement here. Just a sidenote.
> 
> Ah good to know, and yeah that make open some interesting options.
> -Daniel

~~ Lina
  

On Thu, Apr 6, 2023 at 5:45 PM Daniel Vetter <daniel@ffwll.ch> wrote:
>
> Yeah this all looks great and very hyperlinked.
>
> I think the only nit I have is that for types with two or more type
> variables (like the rbtree) what each of them should represent in the top
> intro. I can guess it's <Key, Value> and not the other way round, but
> confirmation takes quite a bit of scrolling to check with the function
> types.

Yeah, that is fair. Personally I prefer more descriptive names when
there are several or they have a special/asymmetric role.

> Otherwise I think perfect api docs.

Glad you like it!

> Just a quick comment on this, that's the same we do on the C side. Most
> overview chapters are actually DOC: sections pulled in from the code.
>
> What I meant here is that for big overview stuff (like for modesetting how
> the display pipe structures tie together as an example:
> https://dri.freedesktop.org/docs/drm/gpu/drm-kms.html#overview)
> it doesn't make sense to duplicate that in rustdoc once more.

Yeah, definitely, if it is already somewhere else for C, we shouldn't
duplicate it (that is what I meant by the "shared across C and Rust"
exception).

> Maybe drm is the exception, but if you look at our .rst files we also have
> most of our docs in the code:
>
> https://cgit.freedesktop.org/drm/drm/tree/Documentation/gpu/drm-kms-helpers.rst
>
> The rst files just provide the scaffolding because C dosn't have
> crates/modules hierarchy that would do this for you automatically.

Sorry, I was talking in general in the kernel. That
`drm-kms-helpers.rst` looks great.

From a quick grep, I think you are indeed one of the big users of
`DOC: `, which indeed map closely to what you would do in Rust without
the scaffolding need.

So I think you will like writing docs in Rust :)

Cheers,
Miguel