Constructing DSTs with Fat Pointers
Table of Contents
What are Dynamically Sized Types?
Imagine you were tasked with writing an implementation of the UDP protocol, you would need to be able to both send and recieve packets. How could you model the following UDP packet as a structure in your code?
| Bit | +0..7 | +8..15 | +16..23 | +24..32 |
|---|---|---|---|---|
| 0 | Source Port | Destination Port | ||
| 32 | Length | Checksum | ||
| ... | Payload | |||
https://hpbn.co/building-blocks-of-udp/#udp-header
The header portion of the packet is pretty simple, however the payload is where things become tricky. We can’t use the most obvious choice of an fixed-size array, because we don’t know the size at compile time, it’s described by the length field in the header!
struct udp_packet {
uint16_t source;
uint16_t dest;
uint16_t len;
uint16_t check;
uint8_t payload[?];
};
So the next obvious choice is to use a dynamically allocated array:
struct udp_packet {
uint16_t source;
uint16_t dest;
uint16_t len;
uint16_t check;
uint8_t* payload;
};
But, this doesn’t seem quite right either. The packet itself should contain the payload - not a pointer to the payload’s data. Every packet would be using an extra 4/8-bytes of memory, and would also cause the heap to slightly more fragmented than if it was stored contiguously.
There is third option though, the flexible array member:
struct udp_packet {
uint16_t source;
uint16_t dest;
uint16_t len;
uint16_t check;
uint8_t payload[];
};
This structure is unlikely to appear in actual implementations, this is purely demonstrative. Taking a quick look at linux/udp.h shows that the packet and header portion are seperated, for various reasons. Rarely, you may see the odd non-standard zero-sized array, or an array with a size of 1 to mark the end of a header.
Perfect, now lets create a packet to send over a network:
int main() {
uint8_t payload[5] = { 5, 5, 5, 5, 5 };
struct udp_packet packet = { 0, 0, 0, 0, payload };
}
<source>: In function 'main':
<source>:13:46: error: non-static initialization of a flexible array member
13 | struct udp_packet packet = { 0, 0, 0, 0, payload };
| ^~~~~~~
<source>:13:46: note: (near initialization for 'packet')
Compiler returned: 1
… Right, we can’t create construct the packet ordinally, the compiler cant know how much space to reserve to reserve on the stack:
main:
push rbp
mov rbp, rsp
; Payload
mov DWORD PTR [rbp-5], 84215045
mov BYTE PTR [rbp-1], 5
; Packet
mov WORD PTR [rbp-?], 1
mov WORD PTR [rbp-?], 2
mov WORD PTR [rbp-?], 3
mov WORD PTR [rbp-?], 4
;mov WORD PTR [rbp-?], payload
mov eax, 0
pop rbp
ret
No big deal, just allocate it on the heap like you would with any other dynamic array:
int main() {
uint8_t payload[5] = { 5, 5, 5, 5, 5 };
int len = sizeof(struct udp_packet) + (sizeof(payload) / sizeof(payload[0]));
struct udp_packer* packet = malloc(len);
}
DSTs in Rust
While this is not an previous implementation is not ideal, it is relatively straight forward in C. However, C is not the only language with conceptions of dynamically sized types - let’s try this again in Rust and how quickly things can get messy.
I’m going to move away from the UDP packet terminology for now, because there are other use cases for these dynamically-sized types. But the rest of the concepts stay the same, the type must be dynamic in size, and we should be able to construct and recieve/parse these types.
Here’s what the same structure would look like in Rust:
pub struct Header {
len: u32,
payload: [u8],
}
This actually looks quite nice, much friendlier than the reference counterpart that
stores the payload seperately (C equivalent to the uint8_t *payload version):
pub struct Header<'a> {
len: u32,
payload: &'a [u8]
}
Cool, now let’s try to construct it. Rust provides a smart-pointer type Box<T> for allocations
so let’s make use of it:
fn main() {
pub struct Header {
len: u32,
payload: [u8],
}
fn main() {
let allocated_header = Box::new(
Header {
len: 5,
payload: [1, 2, 3, 4, 5]
}
);
}
}
error[E0308]: mismatched types
--> <source>:10:22
|
10 | payload: [1, 2, 3, 4, 5]
| ^^^^^^^^^^^^^^^ expected `[u8]`, found `[u8; 5]`
error[E0277]: the size for values of type `[u8]` cannot be known at compilation time
--> <source>:8:9
|
8 | / Header {
9 | | len: 5,
10 | | payload: [1, 2, 3, 4, 5]
11 | | }
| |_________^ doesn't have a size known at compile-time
|
= help: within `Header`, the trait `Sized` is not implemented for `[u8]`, which is required by `Header: Sized`
note: required because it appears within the type `Header`
--> <source>:1:12
|
1 | pub struct Header {
| ^^^^^^
= note: structs must have a statically known size to be initialized
error: aborting due to 2 previous errors
Some errors have detailed explanations: E0277, E0308.
For more information about an error, try `rustc --explain E0277`.
Okay the compiler is hinting at the problem, but why can’t we actually allocate our struct? This is one of the less intuative compiler messages I have seen. The Rustonomicon has a section on this though, this should clear things up.
Currently the only properly supported way to create a custom DST is by making your type generic and performing an unsizing coercion: … (Yes, custom DSTs are a largely half-baked feature for now.)
… Okay, let’s take another stab at it, following the Nomicon’s example:
#[derive(Debug)] // <- This allows the struct to be printed with the debug (:?) format specifier
pub struct Header<T: ?Sized> { // <- Introduce a generic T, and remove the Sized requirement for the type
len: u32,
payload: T,
}
fn main() {
// First, we need to create the sized version of the structure
let sized: Header<[u8; 5]> = Header {
len: 5,
// This is just an array [u8; T], not a slice of an array [u8]
payload: [1, 2, 3, 4, 5],
};
// Coerce the sized version of the structure, into the unsized variant
let dynamic: &Header<[u8]> = &sized;
println!("{:?}", dynamic);
}
Program returned: 0
Program stdout
Header { len: 5, payload: [1, 2, 3, 4, 5] }
So what exactly is an unsized coercion?
In short, arrays ([T; N]) implement the trait Unsize<[T]>,
and for builtin pointer types, pointers of T will coerce to pointers of U if T: Unsize<U> by
converting from a thin pointer to a fat pointer, as stated in the documentation.
This will be explorer further in the Thin to Fat Pointers section.
Despite the type theory, this is very convienant. Prior to the RFC
that implemented this feature, we would have to manually allocate the type given the layout of the Header structure.
This is much closer to how we originally allocated it in C, by calculating it’s size - except in Rust there
manages to include even more footguns.
Manually allocating the struct would look something like:
❗⚠️ Do not use the following code. ⚠️❗
#![feature(alloc_layout_extra, ptr_metadata)]
extern crate alloc;
#[derive(Debug)]
struct Header {
len: u32,
payload: [u8],
}
impl Header {
fn boxed_from_slice(payload: &[u8]) -> Box<Self> {
use alloc::alloc::{alloc, handle_alloc_error};
use core::{
alloc::Layout,
ptr::{copy_nonoverlapping, from_raw_parts_mut, NonNull},
};
let layout = Layout::new::<u32>()
.extend(Layout::new::<u8>().repeat(payload.len()).unwrap().0).unwrap().0
.pad_to_align();
// SAFETY: layout has nonzero size because it fits at least
// the 'len' field (u32).
let ptr = match NonNull::new(unsafe { alloc(layout) }) {
None => handle_alloc_error(layout),
Some(ptr) => from_raw_parts_mut::<Self>(ptr.as_ptr() as *mut (), payload.len()),
};
// SAFETY: ptr points to allocated (but not initialized) Dst
unsafe {
let len_ptr = &raw mut (*ptr).len;
len_ptr.write(payload.len() as u32);
// Initialize the DST part of the header (payload)
let tail_ptr = &raw mut (*ptr).payload;
copy_nonoverlapping(payload.as_ptr(), tail_ptr as _, payload.len());
}
// SAFETY: ptr points to an allocated Dst, and all fields have been initialized
unsafe { Box::from_raw(ptr) }
}
fn boxed_from_array<const LEN: usize>(payload: [u8; LEN]) -> Box<Self> {
use alloc::alloc::{alloc, handle_alloc_error};
use core::{
alloc::Layout,
ptr::{copy_nonoverlapping, from_raw_parts_mut, NonNull},
};
let layout = Layout::new::<u32>()
.extend(Layout::new::<u8>().repeat(LEN).unwrap().0).unwrap().0
.pad_to_align();
// SAFETY: layout has nonzero size because it fits at least
// the 'len' field (u32).
let ptr = match NonNull::new(unsafe { alloc(layout) }) {
None => handle_alloc_error(layout),
Some(ptr) => from_raw_parts_mut::<Self>(ptr.as_ptr() as *mut (), LEN),
};
// SAFETY: ptr points to allocated (but not initialized) Dst
unsafe {
let len_ptr = &raw mut (*ptr).len;
len_ptr.write(LEN as u32);
// Initialize the DST part of the header (payload)
let tail_ptr = &raw mut (*ptr).payload;
copy_nonoverlapping(&raw const payload, tail_ptr as _, LEN);
}
// SAFETY: ptr points to an allocated Dst, and all fields have been initialized
unsafe { Box::from_raw(ptr) }
}
}
fn main() {
let from_slice = Header::boxed_from_slice(&[1, 2, 3, 4, 5]);
println!("{:?}", from_slice);
let from_array = Header::boxed_from_array([1, 2, 3, 4, 5]);
println!("{:?}", from_array);
}
Writing code like this is error prone, and should be avoided. However, if you must write unsafe code like this, Miri is a must-have in your toolkit, and can spot soundness issues such as the one introduced in the above example. The undefined behaviour I introduced was not demonstrative, but a real example of how small mistakes are easy for humans to write and one that would have been left in the article if it wasn’t for Miri’s assistance.
The Solution ✅
If you don’t have Miri already installed, add it with rustup +nightly component add miri then run cargo miri run.
error: Undefined Behavior: memory access failed: expected a pointer to 25 bytes of memory, but got alloc9387 which is only 5 bytes from the end of the allocation
--> src/main.rs:69:13
|
69 | copy_nonoverlapping(&raw const payload, tail_ptr as _, LEN);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ memory access failed: expected a pointer to 25 bytes of memory, but got alloc9387 which is only 5 bytes from the end of the allocation
|
= help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
= help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
help: alloc9387 was allocated here:
--> src/main.rs:44:43
|
44 | fn boxed_from_array<const LEN: usize>(payload: [u8; LEN]) -> Box<Self> {
| ^^^^^^^
= note: BACKTRACE (of the first span):
= note: inside `Header::boxed_from_array::<5>` at src/main.rs:69:13: 69:72
note: inside `main`
--> src/main.rs:81:22
|
81 | let from_array = Header::boxed_from_array([1, 2, 3, 4, 5]);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
error: aborting due to 1 previous error
Miri gives a trace, saying that the issue happened in the boxed_from_array method, then directly points
to the core::ptr::copy_nonoverlapping call.
The &raw const payload parameter should be changed to payload.as_ptr() like so:
// Initialize the DST part of the header (payload)
let tail_ptr = &raw mut (*ptr).payload;
copy_nonoverlapping(payload.as_ptr(), tail_ptr as _, LEN);
Thin to Fat Pointers
For the following section, let’s split up our Header structure into it’s Sized and Unsized counterparts:
use core::mem::size_of;
const MAGIC: [u8; 5] = *b"MAGIC";
struct HeaderFields {
magic: [u8; 5], // <- New field!
len: u32,
}
impl HeaderFields {
pub const fn default() -> Self {
Self {
magic: MAGIC,
len: core::mem::size_of::<Self>() as u32,
}
}
}
#[repr(C, packed)]
struct UnsizedHeader {
header: HeaderFields,
payload: [u8],
}
impl UnsizedHeader {
pub unsafe fn from_ptr<'a>(ptr: *const HeaderFields) -> Option<&'a Self> {
unimplemented!()
}
}
We could implement the from_ptr method as such:
pub unsafe fn from_ptr<'a>(ptr: *const HeaderFields) -> Option<&'a Self> {
// We must use core::ptr::slice_from_raw_parts rather than core::slice::from_raw_parts
// or it will violate ...
use core::ptr::slice_from_raw_parts;
// Calculate the length of the payload from the header field
let payload_len = (*ptr).len as usize - size_of::<HeaderFields>();
// Synthesize the fat pointer. We do this by claiming we have a direct
// pointer to a [T], and then changing the type of the borrow. The key
// point here is that the length portion of the fat pointer applies
// only to the number of elements in the dynamically-sized portion of
// the type, so the value will be the same whether it points to a [T]
// or something else with a [T] as its last member.
let slice = slice_from_raw_parts(ptr.cast::<u8>(), payload_len);
let fat_ptr = slice as *const [u8] as *const Self;
let unsized_header = &*fat_ptr;
match unsized_header.fields.magic {
MAGIC => Some(unsized_header),
_ => None,
}
}
It used to be that slice as *const [u8] as *const Self used to not be well-defined, but seems as of this PR
this is no longer the case.
slice::from_raw_parts vs. ptr::slice_from_raw_parts
error: Undefined Behavior: trying to retag from <1585> for SharedReadOnly permission at alloc4[0x0], but that tag does not exist in the borrow stack for this location
--> src/main.rs:44:30
|
44 | let unsized_header = &*fat_ptr;
| ^^^^^^^^^
| |
| trying to retag from <1585> for SharedReadOnly permission at alloc4[0x0], but that tag does not exist in the borrow stack for this location
| this error occurs as part of retag at alloc4[0x0..0xc]
|
= help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
= help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <1585> would have been created here, but this is a zero-size retag ([0x0..0x0]) so the tag in question does not exist anywhere
--> src/main.rs:42:23
|
42 | let fat_ptr = slice as *const [u8] as *const Self;
| ^^^^^
= note: BACKTRACE (of the first span):
= note: inside `UnsizedHeader::from_ptr::<'_>` at src/main.rs:44:30: 44:39
note: inside `main`
--> src/main.rs:56:27
|
56 | let header = unsafe { UnsizedHeader::from_ptr(ptr) }.unwrap();
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace
error: aborting due to 1 previous error
#[link_section = ".my_section"]
static HEADER: HeaderFields = HeaderFields::default();
fn main() {
let ptr = &raw const HEADER;
let header = unsafe { UnsizedHeader::from_ptr(ptr) };
}
use core::mem::size_of;
const MAGIC: [u8; 5] = *b"MAGIC";
#[derive(Debug)]
struct HeaderFields {
magic: [u8; 5], // <- New field!
len: u32,
}
impl HeaderFields {
pub const fn default() -> Self {
Self {
magic: MAGIC,
len: core::mem::size_of::<Self>() as u32,
}
}
}
#[repr(C)]
struct UnsizedHeader {
pub fields: HeaderFields,
pub payload: [u8],
}
impl UnsizedHeader {
pub unsafe fn from_ptr<'a>(ptr: *const HeaderFields) -> Option<&'a Self> {
// We must use core::ptr::slice_from_raw_parts rather than core::slice::from_raw_parts
// or it will violate ...
use core::ptr::slice_from_raw_parts;
// Calculate the length of the payload from the header field
let payload_len = (*ptr).len as usize - size_of::<HeaderFields>();
// Synthesize the fat pointer. We do this by claiming we have a direct
// pointer to a [T], and then changing the type of the borrow. The key
// point here is that the length portion of the fat pointer applies
// only to the number of elements in the dynamically-sized portion of
// the type, so the value will be the same whether it points to a [T]
// or something else with a [T] as its last member.
let slice = slice_from_raw_parts(ptr.cast::<u8>(), payload_len);
let fat_ptr = slice as *const [u8] as *const Self;
// Create reference from the pointer to the DST
let unsized_header = &*fat_ptr;
// Ensure our magic is what we expected
match unsized_header.fields.magic {
MAGIC => Some(unsized_header),
_ => None,
}
}
}
static HEADER: HeaderFields = HeaderFields::default();
fn main() {
let ptr = &raw const HEADER;
let header = unsafe { UnsizedHeader::from_ptr(ptr) }.unwrap();
println!("{:?}", &header.fields);
}