This document outlines how the Linux Kernel is using the unstable features arbitrary-self-types and dispatch_from_dyn/unsize.
But first, an introduction to the custom types that the Kernel is using.
(The pre-meeting version of this document is here: https://hackmd.io/cuKNW7xxRzGsOUMiThs73w)
The Linux Kernel needs to use a custom implementation of Arc. The most important reason is that we need to use the Kernel's refcount_t type for the atomic instructions on the refcount. There are two reasons for this:
Arc will call abort on overflow. This is not acceptable in the Kernel; instead we want to saturate the count when it hits isize::MAX. This effectively leaks the Arc.asm! block or similar that matches what Kernel C does, rather than an LLVM intrinsic.We also make a few other changes to our Arc:
Arc is implicitly pinned.Our Arc also comes with two utility types:
ArcBorrow<'a, T>. Similar to &'a Arc<T>, but only one level of indirection.UniqueArc<T>. Mutable access to an Arc. Used to split allocation and initialization into two steps, which is important since we cannot allocate memory while holding a spinlock.The Kernel uses a lot of intrusive linked lists, which are extremely rare in userspace Rust. This is a consequence of a unique limitation in kernel code related to memory allocations:
(Technically there are special ways to allocate memory in atomic context, but it should be used sparingly.)
These limitations greatly affect how we design code in the kernel. There are some functions where having a failure path is not acceptable (e.g. destroying something), and other places where we cannot allocate at all. This means that we need data structures that do not need to allocate. Or where the allocation and insert steps are separate. Imagine a map protected by a spinlock. How do you implement that if insert simply cannot allocate memory?
One answer to this is to use a linked list (and similar, e.g. a red/black tree can work with the same idea). The value you wish to insert takes this form:
struct MyValue {
// In practice, these are wrapped into one field using a struct.
next: *mut MyValue,
prev: *mut MyValue,
foo: Foo,
bar: Bar,
}
Then, given an Arc<MyValue>, you can insert that into a linked list without having to allocate memory. The only thing you have to do is adjust the next/prev pointers.
Additionally, there are a bunch of C apis that work using the same principle, so we are also forced into this pattern when we want to use those C apis. For example, this includes the workqueue which stores the list of tasks to run in a linked list.
You may have noticed one problem with the above design: The value we are inserting is an Arc<MyValue>, so how can you get mutable access to next/prev? And how do you know that it's not already in a linked list? What about data races — someone could attempt to push (two clones of) the same Arc<MyValue> to two different linked lists, which would constitute a data race on the next/prev fields.
You could solve these issues by adding an AtomicBool for keeping track of whether it is in a list, but this isn't great. We really want to avoid the AtomicBool.
Our answer is another custom smart pointer type: ListArc. The ListArc type is just a newtype wrapper around Arc with the invariant that each MyStruct has at most one ListArc reference. However, unlike UniqueArc, you are allowed to have Arc references to a value that also has an ListArc. This way, the ListArc reference can be given exclusive access to the next/prev fields, which is enough to design a safe API for intrusive linked lists containing reference counted values.
One consequence of this is that (unlike Arc), we are using a smart pointer where ownership of the pointer is extremely important. You cannot just clone a ListArc.
Our ListArc type also has a second generic parameter, which allows you to have multiple next/prev pairs. So ListArc<T, 1> has exclusive access to the first next/prev pair, and ListArc<T, 2> has exclusive access to the second such pair. This means that you can have multiple list arcs as long as their parameter is different (one per value of the extra generic parameter).
We want to be able to use linked lists with dyn Trait. However, the offset of the next/prev fields needs to be uniform no matter what the concrete type is. To do that, we use a wrapper type:
struct Wrapper<T: ?Sized> {
next: *mut Wrapper<T>,
prev: *mut Wrapper<T>,
value: T,
}
And the actual type ends up being Arc<Wrapper<dyn Trait>>.
We wish to use arbitrary self types in various places. Some examples:
self.clone() and get a new Arc to the current struct. To do that, we need self: &Arc<T> or self: ArcBorrow<'_, T>.linked_list.push(self). To do that, we need self: ListArc<T>.For the struct methods, we could work around this by not using self parameters, and calling MyStruct::foo(my_arc). However, we also need to do these things in traits where we perform dynamic dispatch on the value. For example:
trait WorkItem {
fn run1(self: ListArc<Self>);
// or, actually:
fn run2(self: ListArc<Wrapper<Self>>);
}
This use-case needs both arbitrary self types and the dynamic dispatch feature mentioned in the next section. Arbitrary self types are needed because dynamic dispatch is only performed on self parameters.
We wish to use these linked lists to store dynamic trait objects. This is used for a "todo list" of events that need to be delivered to userspace. There are many different event types, and we use a trait object to store a queue of them.
There is a need to have both Arc<MyStruct> and Arc<dyn MyTrait> references to the same object.
All of the smart pointers that we want to use dynamic dispatch with are newtype wrappers around either NonNull or other smart pointers (e.g. ListArc is a wrapper around Arc). They may also have a PhantomData field. These requirements match what is listed on DispatchFromDyn.
A related feature is the Unsize trait. Most likely, adding the DispatchFromDyn trait depends on also having Unsize, so we need it for that reason. But we do not otherwise need the Unsize trait.
Stabilizing the entire DispatchFromDyn trait may not be necessary for stabilizing enough for what the kernel needs. One suggestion by compiler-errors is as follows:
#[derive(SmartPointer)]
struct Foo<#[pointee] T> {
ptr: *const T,
}
As an initial solution, we could stabilize a derive macro for creating smart pointers without stabilizing the underlying DispatchFromDyn and Unsize traits themselves.
The kernel also has some other uses of dynamic dispatch that trait objects don't help with. Mainly, these are cases where C defines a vtable using a struct with function pointers. Here, we must match the vtable layout that C dictates, so we will manually implement the vtable unsafely to handle these cases. We still use a trait for providing a safe API to these things, but the implementation needs only generics and not trait objects.
However, for Rust-to-Rust dynamic dispatch, trait objects appear to satisfy our needs. As long as we are able to use them with our smart pointers, that is.
derive(SmartPointer) proposal work for Rust-for-Linux?Josh: Would like to check whether providing this in stable Rust seems likely to meet Rust-for-Linux's needs, without needing to stabilize the full DispatchFromDyn. derive(SmartPointer) could enforce the requirements needed for that to be sound.
Gary: I guess that depends on the detail of the derive(SmartPointer). Will it work for all cases covered by today's DispatchFromDyn and CoerceUnsized implemented-together? I.e. will it cover both raw pointers, NonNulls and types that are themselves wrapper of pointer types?
Josh: We were I think hesitant to stabilize DispatchFromDyn due to the large number of unsafe criteria that have to be satisfied, and whether this was the right interface. Adding a derive here could allow us to enforce those.
Alice: What we really need here are raw pointers to work with dynamic dispatch.
Josh: We can iterate with Rust-for-Linux folks to try to cover the specific needs.
nikomatsakis: I think it'd be really useful to have some medium-length snippet of code (or multiple small snippets) showing how these arcs are used in practice. Like how they're allocated, inserted, etc.
Alice: The binder driver is a good example of this. The process has references to all of the threads. Then it has a stack (list) of threads ("ready threads") that can receive incoming transactions right now.
Alice: The key use case here are events that we need to insert and remove from lists, e.g. "deliver to read".
NM:
Patterns Niko wants to see:
MyType example below)E.g.:
let deliver_to_read: List<dyn Event, 1> = List::new();
let item: ListArc<Wrapper<T>, 1> = some_list_arc;
let item: ListArc<Wrapper<dyn Event>, 1> = some_list_arc;
deliver_to_read.insert(item)
impl<T, const N: usize> List<T, N>
where
T: ?Sized + ListItem<N>,
{
fn insert(list: ListArc<T, N>) {
}
}
#[repr(C)]
pub struct Wrapper<T> {
prev: *const Wrapper<T>,
next: *const Wrapper<T>,
value
}
unsafe impl<T: ?Sized> ListItem<1> for Wrapper<T> {
const PREV_OFFSET = 0;
}
unsafe trait ListItem<const N: usize> {
const PREV_OFFSET: usize;
}
Unsize traitNM: We didn't really talk about this.
Alice: We don't use this directly. But it comes up with DispatchFromDyn. If a macro generates these, then all of our users of this go away.
Gary: If we could use our Arc on stable with dynamic dispatch, we could probably work around the other issues.
NM: The first step is to get code examples.
NM: Then, what CE suggested with respect to the derive macro seems feasible. I'd like to play around with that.
Gary: What are the obstacles to stabiling the feature as is?
NM: Unsize probably has fewer questions. There's also CoerceUnsized. For DispatchFromDyn, there are just more questions.
NM: To meet the needs of RfL here, we don't need to stabilize the traits in full, so it makes sense to keep flexibility here.
NM: Do your types implement Deref?
Alice: Yes.
Gary: When we wrap a C struct, we put it into an "opaque" wrapper, which is UnsafeCell + MaybeUninit + !Unpin.
Alice: There's some relation to UnsafeAliased from RalfJ here.
NM: Intrusive linked lists will want to allow mut pointers from the outside which needs similar pinning guarantees to our Futures.
TC: We might discuss the issue of raw pointers and NonNull for arbitrary self types, since we were leaning a direction there.
NM: (Fills in background.)
Gary: This largely isn't an issue for us, though we might want dynamic dispatch on raw pointers.
Alice: We could always use a newtype.
Gary: Yes, we could put another opaque wrapper around it.
NM: Who should lead putting together a proposal here?
Josh: CE is one option, of course, if interested. The author of the arbitrary self types proposal is also interested in pushing things forward. We should at least get feedback from these parties. CE in particular knows what requirements are needed to make things sound.
TC: Adrian has been working with the RfL team. He might be willing to take this and work with CE on it.
NM: +1. It'd be good to ensure this also meets the CppRef use case.
Lukas: I'd also be happy to help here.
NM: Maybe it'd be useful for us to have libprocmacro so that you have to explicitly pull this into scope. That may make it easier for us to deprecate this if needed. But I like the idea of exposing macros for these kind of use cases so we can leave ourselves more room on other design questions.
(The meeting ended here.)
nikomatsakis: The doc says:
We wish to use arbitrary self types in various places. Some examples:
- Many methods need to call
self.clone()and get a newArcto the current struct. To do that, we needself: &Arc<T>orself: ArcBorrow<'_, T>.- We often need to do
linked_list.push(self). To do that, we needself: ListArc<T>.
For that first point, this is not obviously covered by existing proposals, right? What seems to be missing is wanting something like "auto-deref" to from Arc<T> to ArcBorrow<'_, T>? i.e., I imagine you want to be able to do:
impl MyType {
fn clone(self: ArcBorrow<'_, Self>) -> Arc<Self> {
...
}
}
let x: Arc<MyType> = ...;
x.clone() // ?
Alice: Here we just do the inconvenient thing and explicitly convert to ArcBorrow.
Gary: I recall that we discussed about the idea of exposing &ArcInner in RfL meeting. @Wedson I didn't exactly recall but what issue did we find with that issue?
Boqun: Pointer provenance.
Gary: Ah yes, so this rhymes with the discussion on having arbitrary self type that works with types that do not create reference.
ArcBorrow?Josh: Could we get the struct definition for ArcBorrow? Is there some way we could reduce indirection without needing a unique type?
Alice:
pub struct ArcBorrow<'a, T: ?Sized + 'a> {
inner: NonNull<ArcInner<T>>,
_p: PhantomData<&'a ()>,
}
nikomatsakis: To confirm, you say that dyn meets your needs, but you are anticipating "wide pointer"-style semantics?
Alice: Yes, our uses of dyn are wide pointers. The places where this might be a potential problem are also places where we have to do it manually anyway because C defines the layout of the vtable.
nikomatakis: I want to be sure I understand the set of types as things are currently setup. It seems like there is…
Arc<T> which is in fact an alias for ArcInner<Wrapper<T>>Wrapper which adds the next/prev fields – and presumably there is sometimes space for more than one.ArcInner in some sense./// Stores an opaque value.
///
/// This is meant to be used with FFI objects that are never interpreted by Rust code.
#[repr(transparent)]
pub struct Opaque<T> {
value: UnsafeCell<MaybeUninit<T>>,
_pin: PhantomPinned,
}
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe