[Pre-RFC] Custom DSTs


#1

Summary

Allow Rust code to define dynamically sized types with custom thick (and thin) pointers, and define slice functions in terms of these, instead of transmute. Also, convert the CStr type to use this functionality, and make it a thin pointer; this will allow use with FFI.

Motivation

As of right now, the lack of custom DSTs in Rust means that we can’t communicate with C in important ways - we lack the ability to define a CStr in the language such that &CStr is compatible with char const *, and we lack the ability to communicate nicely with C code that uses Flexible Array Members. This RFC attempts to fix this, as well as introduce more correctness to existing practices.

Apart from FFI, it also has usecases for indexing and slicing 2-d arrays.

Guide-level explanation

There’s a new language trait in the standard library, under std::ops:

unsafe trait DynamicallySized {
    type Metadata: 'static + Copy;

    fn size_of_val(&self) -> usize;
    fn align_of_val(&self) -> usize;
}

with an automatic implementation for all Sized types:

unsafe impl<T> DynamicallySized for T {
    type Metadata = ();

    fn size_of_val(&self) -> usize { size_of::<T>() }
    fn align_of_val(&self) -> usize { align_of::<T>() }
}

If you have a type which you would like to be unsized, you can implement this trait for your type!

#[repr(C)]
struct CStr([c_char; 0]);

unsafe impl DynamicallySized for CStr {
    type Metadata = ();

    fn size_of_val(&self) -> usize { strlen(&self.0 as *const c_char) }
    fn align_of_val(&self) -> usize { 1 }
}

and automatically, your type will not implement Sized.

The existing DynamicallySized types will continue to work; if one writes a DynamicallySized type T, and then wraps T into a struct, they’ll get the obvious semantics.

struct Foo {
    x: usize,
    y: CStr,
}

// size_of_val(&foo) returns size_of::<usize>() + size_of_val(&foo.y)
// same with align_of_val

More Examples

Non-trivial types

For non-trivial types (i.e., those that have a destructor), Rust generates the obvious destructor from the definition of the type itself - i.e., if you hold a Vec<T> in your type, Rust will destroy it. However, if your type contains additional data that Rust doesn’t know about, you’ll have to destroy it yourself.

#[repr(C)] // we need this to be laid out linearly
struct InlineVec<T> {
    capacity: usize,
    len: usize,
    buffer: [T; 0], // for offset, alignment, and dropck
}

unsafe impl<T> DynamicallySized for InlineVec<T> {
    type Metadata = ();

    fn size_of_val(&self) -> usize {
        Self::full_size(self.capacity)
    }
    fn align_of_val(&self) -> usize {
        Self::full_align()
    }
}
impl<T> Drop for InlineVec<T> {
    fn drop(&mut self) {
        std::mem::drop_in_place(self.as_mut_slice());
    }
}

impl<T> InlineVec<T> {
    // internal
    fn full_size(cap: usize) -> usize {
        std::mem::size_of_header::<Self>() + cap * std::mem::size_of::<T>()
    }
    fn full_align() -> usize {
        std::mem::align_of_header::<Self>().max(std::mem::align_of::<T>())
    }

    pub fn new(cap: usize) -> Box<Self> {
        let size = Self::full_size(cap);
        let align = Self::full_align();
        let layout = std::alloc::Layout::from_size_align(size, align).unwrap();
        let ptr = std::raw::from_raw_parts_mut(std::alloc::alloc(layout) as *mut (), ());
        std::ptr::write(&mut ptr.capacity, cap);
        std::ptr::write(&mut ptr.len, 0);
        Box::from_raw(ptr)
    }

    pub fn len(&self) -> usize {
        self.len
    }
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn as_ptr(&self) -> *const T {
        &self.buff as *const [T; 0] as *const T
    }
    pub fn as_mut_ptr(&mut self) -> *mut T {
        &mut self.buff as *mut [T; 0] as *mut T
    }

    pub fn as_slice(&self) -> &[T] {
        unsafe {
            std::slice::from_raw_parts(self.as_ptr(), self.len())
        }
    }
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        unsafe {
            std::slice::from_raw_parts(self.as_mut_ptr(), self.len())
        }
    }

    // panics if it doesn't have remaining capacity
    pub fn push(&mut self, el: T) {
        assert!(self.size() < self.capacity());
        let ptr = self.as_mut_ptr();
        let index = self.len();
        std::ptr::write(ptr.offset(index as isize), el);
        self.len += 1;
    }

    // panics if it doesn't have any elements
    pub fn pop(&mut self) -> T {
        assert!(self.len() > 0);
        self.len -= 1;
        let ptr = self.as_mut_ptr();
        let index = self.len();
        std::ptr::read(ptr.offset(index as isize))
    }
}

Reference-level explanation

In addition to the explanation given above, we will also introduce three functions into the standard library, in core::raw, which allow you to create and destructure these pointers to DynamicallySized types:

mod core::raw {
    pub fn from_raw_parts<T: DynamicallySized>(
        ptr: *const (),
        meta: <T as DynamicallySized>::Metadata,
    ) -> *const T;

    pub fn from_raw_parts_mut<T: DynamicallySized>(
        ptr: *mut (),
        meta: <T as DynamicallySized>::Metadata,
    ) -> *mut T;

    pub fn metadata<T: DynamicallySized>(
        ptr: *const T,
    ) -> <T as DynamicallySized>::Metadata;
}

and we will introduce two functions into core::mem, to help people write types with Flexible Array Members:

mod core::mem {
    pub fn size_of_header<T: DynamicallySized>() -> usize;
    pub fn align_of_header<T: DynamicallySized>() -> usize;
}

These functions return the size and alignment of the header of a type; or, the minimum possible size and alignment, in other words. For existing Sized types, they are equivalent to size_of and align_of, and for existing DSTs,

assert_eq!(size_of_header::<[T]>(), 0);
assert_eq!(align_of_header::<[T]>(), align_of::<T>());
assert_eq!(size_of_header::<dyn Trait>(), 0);
assert_eq!(align_of_header::<dyn Trait>(), 1);

// on 64-bit
assert_eq!(size_of_header::<RcBox<dyn Trait>>(), 16);
assert_eq!(align_of_header::<RcBox<dyn Trait>>(), 8);

Notes:

  • names of the above functions should be bikeshed
  • extern types do not implement DynamicallySized, although in theory one could choose to do this (that usecase is not supported by this RFC).
  • T: DynamicallySized bounds imply a T: ?Sized bound.

We will also change CStr to have the implementation from above.

On an ABI level, we promise that pointers to any type with

size_of::<Metadata>() == 0
&& align_of::<Metadata>() <= align_of::<*const ()>()

are ABI compatible with a C pointer - this is important, since we want to be able to write:

extern "C" {
    fn printf(fmt: &CStr, ...) -> c_int;
}

Unfortunately, we won’t be able to change existing declarations in libc without a new major version.

as casts continue to allow

fn cast_to_thin<T: DynamicallySized, U: Sized>(t: *const T) -> *const U {
    t as *const U
}

so we do not introduce any new functions to access the pointer part of the thick pointer.

Drawbacks

  • More complication in the language.
  • Lack of a Sized type dual to these unsized types – the lack of a [u8; N] to these types’ [u8] is unfortunate.
  • Inability to define a custom DST safely
  • The size_of_val and align_of_val declarations are now incorrect; they should take T: DynamicallySized, as opposed to T: ?Sized.

Rationale and alternatives

This has been a necessary change for quite a few years. The only real alternatives are those which are simply different ways of writing this feature. We need custom DSTs.

We also likely especially want to deprecate the current ?Sized behavior of size_of_val and align_of_val, since people are planning on aborting/panicking at runtime when called on extern types. That’s not great. (link)

Prior art

(you will note the incredible number of RFCs on this topic – we really need to fix this missing feature)

Unresolved questions

  • How should these thick pointers be passed, if they are larger than two pointers? (repr(Rust) aggregate)
  • Are std::raw::ptr and std::raw::ptr_mut necessary? You can get this behavior with as. (removed)

Future possibilities

  • By overloading DerefAssign, we could add a BitReference type

#2

Previous discussion: Pre-eRFC: Let's fix DSTs

(BTW I have an alternative design which will be based on RFC 2580, maybe I should update it this weekend :neutral_face:)


Another [Pre-RFC] Custom DSTs
#3

I would like to see this. I have a crate that implements (more or less) every kind of FFI string that would benefit from this. Aside from the exact names used †, and the presence of align_of_val (which I’m not convinced is needed; are there any plausible DSTs with varying alignment?), this is exactly what I’ve considered myself.


†: so temping but, no… mustn’t derail with a bikeshed… :stuck_out_tongue:


#4

That’s how the language works - you can’t, for example, write align_of::<[u8]>(). The DSTs with varying alignment are trait objects, and thin trait objects will be the same.


#5

I messed up phrasing that. DSTs are constructed out of sized values, at which point the needed alignment is known. What does the compiler/runtime need the alignment of the underlying value for? Is it to support hypothetically being able to copy/move DSTs?


#6

I don’t have strong opinions on the precise design, but I’m glad to see this problem get some more attention.

I would like to mention that it is sometimes useful to have dynamically-sized types that don’t have pointers in the traditional sense. I’m mostly thinking about cases where the ‘pointer’ member points to some other memory space (eg. GPU memory) which is not directly accessible. In this case, the pointer is still represented as a *mut T, but it’s not dereferenceable. We still need the fat-pointer behavior in order to make such types work nicely with Deref and DerefMut (which must return &T and &mut T respectively, for some type T). For example, a GPUArray<T> type might want to Deref-coerce to &GPUSlice<T> and &mut GPUSlice<T> (where GPUSlice<T> is a custom DST) the same way normal arrays deref-coerce to &[T].

We should not make an assumption that the “pointer” member is valid to dereference. In a perfect world, we might not assume that it’s even a *mut T pointer at all, but that may not be practical. This proposal doesn’t seem to make that assumption so far, so I’d like to keep it that way.


#7

Mostly, for allocation purposes (basically the same reason we need size_of_val)


#8

If you create an x: &T, it must be valid to dereference at least size_of_val(x) bytes, under alignment align_of_val(x). If you have size_of_val(x) = 0, and align_of_val(x) = 1, then you should be fine :slight_smile: (as long as you don’t have a null pointer value as a reference).


#9

That’s good, thanks. I don’t think I really understand why that would be the case, though. This RFC draft doesn’t go into much detail on what size_of_val and align_of_val would be used for. What sort of code would you expect to call those functions, and what guarantees can that code depend on? It might be useful to add that information to the RFC, since there seems to be some confusion about it.


#10

Any code that does allocation/deallocation calls these functions, I think? They already exist in the standard library: https://doc.rust-lang.org/stable/std/mem/fn.align_of_val.html and https://doc.rust-lang.org/stable/std/mem/fn.size_of_val.html.

They’re frankly not super useful, but these functions are guaranteed to exist, and are necessary for specifically allocation and deallocation.


#12

Just some minor editorial notes:

I assume it returns size_of::<usize>() + size_of_val(&foo.y)?

You are listing five.


#13
  • The size_of_val and align_of_val declarations are now incorrect; they should take T: DynamicallySized , as opposed to T: ?Sized .

Is this a breaking change ?

All other points are just nitpicks that you might want to improve for the RFC. Thank you a lot for working on this. This is great.


In the Foo example, size_of_val(&foo) result appears incorrect (the size of usize is missing) - would be cool to work out this example fully for the RFC.


Are std::raw::ptr and std::raw::ptr_mut necessary? You can get this behavior with as.

You just said they aren’t, so why add them ? People should be using as for this already, so I think it would be better to just add an example that shows that as just works.


How should these thick pointers be passed, if they are larger than two pointers?

IIUC these don’t have to be C FFI safe for the short-term goals of the RFC, so we would be talking here about repr(Rust) only. I don’t see any reason why these couldn’t be passed as aggregates with an unspecified layout. After the RFC, we could specify these further as part of the unsafe code guidelines, but this does not have to be done right now.


we will also introduce four functions into the standard library, in std::raw:

I don’t see any reason to put these in libstd and not libcore, so that should probably be core::raw


Flexible Array Members

In the introduction you might want to mention “(similar to C VLAs)” since VLAs is what people know, but FAM is probably a too technical term, for the introduction at least. Linking the FAM paper (and C VLAs) from the introduction might be worth it.

indexing and slicing 2-d arrays

If you need more examples, you can add one for writing a DST for 2d arrays - that shouldn’t be too hard. If you want to mention more use cases, multi-dimensional slices in general, and maybe “growable” slices (e.g. a slice into a growable Vec/ArrayVec/SmallVec with fixed-capacity).


Prior art

I know you are aware of all previous RFCs on this topic, so you might want to reference some of that here. In particular, the last RFC about this, and @nikomatsakis comments about it at the end, and maybe address what has changed.


#14

@kennytm @ubsan is there a need for a DST working group ? It might make sense to just open an RFC repo for this given the amount of work that has been done already on this subject (many RFCs, pre-RFCs, discussions, etc.) so that those interested can work together in a proposal that has consensus at least among those trying to solve this problem.


#15

To be clear, this does nothing for VLAs. FAMs and VLAs are very, very different features, the first of which is super useful and awesome, the second of which is widely agreed to be a mistake and a massive security risk.

no, because I don’t actually recommend making this change :slight_smile:

I’m just saying it would now be more correct. It would be a breaking change since ?Sized would no longer imply you could call size_of_val on this type.


#16

Maybe slightly off-topic, but I somehow completely missed this memo; what’s wrong with VLAs?


#17

Fairly good write-up here: https://stackoverflow.com/a/21519062

I may have overstated it a bit :stuck_out_tongue:

But yeah, this proposal has nothing to do with VLAs.


#18

Is this behavior worth deprecating so that we can make this breaking change in the future ?

To be clear, this does nothing for VLAs. FAMs and VLAs are very, very different features, the first of which is super useful and awesome, the second of which is widely agreed to be a mistake and a massive security risk.

I don’t disagree, my point was only that FAMs is something that most people haven’t heard about, but VLAs is. I don’t know how to word this, but something like “similar to the good parts of VLAs” or something like that might give people some context to know what this is about.


#19

I strongly believe that it is. The existing proposed behavior of panicking/aborting when called with an invalid type is, frankly, not great.


#20

If anybody would like to write examples, I’m looking for more examples, as well :slight_smile:


#21

One prominent user of size_of_val is Rc::from_box, which converts a Box<T> to Rc<T> by making a new heap allocation and copying the contents (because Rc needs extra space for the reference count), and works for unsized types. It’s also used by Layout::for_value, which is indirectly used in some other places in the standard library for similar purposes.

This functionality has been a headache in general; see also:

IIRC there was at least one scenario where existing code could call it on borrowed references, not just owned smart pointers… or maybe it was just hypothetical; I can’t remember.