custom fat pointers in rust
say you wrote a library that provides zero-copy decoding for some protocol by returning checked and typed “views” into packet buffers:
struct Message<'s>(
/* buffer: */ &'s [u8],
/* question_section: */ Range<usize>,
/* answer_section: */ Range<usize>,
/* authority_section: */ Range<usize>,
/* additional_section: */ Range<usize>,
);
struct Question<'s>(&'s [u8], Range<usize>);
struct Name<'s>(&'s [u8], Range<usize>);
impl<'s> Message<'s> {
fn view(buffer: &'s [u8]) -> Result<Self, ()> {
// TODO: check that the message is valid
Ok(Self(buffer, 12..17, 17..28, 28..28, 28..39))
}
}
impl<'s> Question<'s> {
fn view(buffer: &'s [u8], range: Range<usize>) -> Result<Self, ()> {
// TODO: check that the question is valid
Ok(Self(buffer, 12..17))
}
}
impl<'s> Name<'s> {
fn view(buffer: &'s [u8], range: Range<usize>) -> Result<Self, ()> {
// TODO: check that the name is valid
Ok(Self(buffer, 12..13))
}
}
you can read more about the library in this post, but that design goes a long way. like sure, the lifetimes make the types a bit ugly if you have to refer to them^, but they can be used more or less like normal references, as long as you’re careful when projecting from one view to another [playground]:
// BAD: return value bound by lifetimes of both buffer and self
impl Name<'_> {
// equivalent to impl<'s> Name<'s> { fn parent(&'s self) -> Option<Name<'s>> {} }
fn parent(&self) -> Option<Name<'_>> {
// TODO: skip one label, or return None
Some(Name(self.0, 10..14))
}
}
// GOOD: return value only bound by lifetime of the buffer, not self
impl<'s> Name<'s> {
// equivalent to impl<'s> Name<'s> { fn parent(&'s self) -> Option<Name<'s>> {} }
fn parent(&self) -> Option<Name<'s>> {
// TODO: skip one label, or return None
Some(Name(self.0, 10..14))
}
}
fn cat() -> Option<Name<'static>> {
let name = Name::view(b"\x05daria\x03daz\x03cat\0", 0..15).ok()?;
// BAD version won’t compile:
// error[E0515]: cannot return value referencing temporary value
// error[E0515]: cannot return value referencing local variable
Some(name.parent()?.parent()?)
}
^ you should see the types for zero-copy encoding. now those are ugly :)
but can we do better?
these views are conceptually just newtypes over subslices of the packet buffer, which may need random access to the full packet buffer due to message compression. what if we could define our views as actual rust references with dipping mustards, but with no lifetimes other than the lifetime of the reference itself?
slices in rust are dynamically sized types (“DST”s), and you can even define a custom DST by defining a struct whose last field is a DST, but what we need is a custom fat pointer. while defining a custom fat pointer requires you to define a custom DST, the values of the fat pointers are not simply the values of the DST.
if we want a newtype U where &U is logically a &[T] with some extra metadata and/or type system assertions, and we want a fn(&[T]) -> &U, the extra metadata needs to go in the fat pointer, not in U. one cool example of that approach is bitvec, which encodes bit-in-byte and byte-in-word indices into newtyped slice fat pointers.
unfortunately… there are
three big caveats.
rust provides no stable and officially-sanctioned way to do that, at least until rfc 2580 is stabilised. bitvec relies on the current representation of slice fat pointers, which may change in a future version of rust, requiring a source update.
all fat pointers are currently two pointers wide, so we can only really pack extra metadata into the low-order alignment bits of the pointer, or the second word. there have been ideas for loosening that in this rfc and rfc 1524 and rfc 2594, but for now, two words is all we get.
and if we pack arbitrary metadata into a slice fat pointer, it has to be a [()] pointer internally, not a [T] pointer, otherwise the pointer and length would be invalid. clearly it would require unsafe code, but what’s unclear to me is whether that unsafe code can be sound. for example, miri with stacked borrows rejects the code below (and rejects bitvec), but with tree borrows accepts it. and since the eventual aliasing model will apparently likely fall somewhere “between” stacked borrows and tree borrows, the code below may be unsound.
verdict: not worth doing yet
so if we want a newtype for “subslice” references, the best i can manage is to pack the subslice bounds into the length field, which limits the two indices to u16 each on 32-bit platforms. it currently depends on compiler internals that may change someday, but the only alternative seems to be an unstable feature. and it can’t even fully access the original slice, because there’s no space for the original length.
here’s what that looks like [playground]:
/// conceptually a `&[u8][i..j]` that retains access to the original slice.
pub struct Subslice(#[allow(dead_code)] [()]);
impl Subslice {
pub fn view(source: &[u8], range: impl RangeBounds<usize>) -> &Self {
let range = range.normalise(source);
let range = convert_range_to_u16(range);
let metadata = pack_range_into_slice_pointer_metadata(range);
let result = make_unit_slice_ref(source, metadata);
unsafe { transmute(result) }
}
pub fn range(&self) -> Range<usize> {
let repr: SliceFatPointer = unsafe { transmute(self) };
let range = unpack_range_from_slice_pointer_metadata(repr.len);
range.start.into()..range.end.into()
}
pub fn original_slice(&self) -> &[u8] {
// TODO: can’t get the original len, because we’ve used it for the subslice.
// for now, we just return `&source[0..end]`, which is the best we can do.
let repr: SliceFatPointer = unsafe { transmute(self) };
let source = repr.data as *const u8;
let range = self.range();
unsafe { core::slice::from_raw_parts(source, range.end.into()) }
}
}
fn make_unit_slice_ref(source: &[u8], extra: usize) -> &[()] {
let source = source.as_ptr();
let source: *const () = unsafe { transmute(source) };
// SAFETY: this upholds the invariants of `from_raw_parts`:
// - `data` is non-null, because `source` was a reference, and references are non-null
// - `data` (`source`) is valid for reads for `len * size_of::<T>()` many bytes, because `T`
// is `()`, so the size of `()` is 0, so `len * size_of::<T>()` is 0 for all `len` (`extra`)
// - `data` is properly aligned, because the alignment of `()` is 1
// - ??? does `data` point to `len` consecutive properly initialised values of type `()`?
// it points to properly initialised values of type `T`, which i’m not sure counts?
// - the memory referenced will not be mutated for the duration of the result’s lifetime,
// because the lifetime is set to that of `source` via lifetime elision
// - the total size `len * size_of::<T>()` is not larger than `isize::MAX`, and it will not
// overflow if added to `data`, because it is zero (see above)
unsafe { core::slice::from_raw_parts(source, extra) }
}
fn pack_range_into_slice_pointer_metadata(range: Range<u16>) -> usize {
usize::from(range.start) << 16 | usize::from(range.end)
}
fn unpack_range_from_slice_pointer_metadata(metadata: usize) -> Range<u16> {
let start = u16::try_from(metadata >> 16 & 0xffff).expect("guaranteed by mask");
let end = u16::try_from(metadata & 0xffff).expect("guaranteed by mask");
start..end
}
/// type with identical layout to `&[()]`... for now.
#[repr(C)]
struct SliceFatPointer {
data: *const (),
len: usize,
}
impl AsRef<[u8]> for Subslice {
fn as_ref(&self) -> &[u8] {
let repr: SliceFatPointer = unsafe { transmute(self) };
let source = repr.data as *const u8;
let range = self.range();
let base = unsafe { source.add(range.start.into()) };
let len = range.end - range.start;
unsafe { core::slice::from_raw_parts(base, len.into()) }
}
}
#[test]
fn test() {
let sub: &Subslice = Subslice::view(b"abcdefg", 2..5);
assert_eq!(sub.as_ref(), b"cde");
// TODO: currently fails (see TODO above)
// assert_eq!(sub.original_slice(), b"abcdefg");
assert_eq!(sub.original_slice(), b"abcde");
}