Rust and dynamically-sized thin pointers

Arrays and strings

The simplest DSTs in C are dynamically-allocated arrays, which are simply contiguous sequences of values. The number of values cannot be computed from the array content, so the size (or length) must be passed around as a second parameter to any function that will operate on the array.

bool validate_utf16(uint16_t *values, size_t *values_len) {
	/* size of `*values` is `values_len * sizeof(uint16_t)` */
}

Slightly more complex are arrays terminated by some sentinel value, such as NUL-terminated strings. The size of these values can be computed, but not in constant time – more importantly, the size of a value (1) can change and (2) can be lost. For example a C string can be truncated by writing '\x00' into the middle, and its size can be lost by overwriting the NUL terminator. This property makes traditional C string manipulation code difficult to reason about.

bool validate_utf8(const char *str) {
	/* This call might take a very long time, or even crash the process. */
	size_t str_len = strlen(str);
}

Due to the unpredictable behavior of C string manipulation code, modern systems programming languages generally avoid NUL-termination (or other inline sentinel values). Even in C, newly-written APIs tend to pass around the length explicitly (compare strcat() with strncat() and strlcat()). Many modern C codebases have adopted some form of thick pointer idiom for dynamically-sized values, for example GLib's GByteArray and GString.

struct GByteArray {
	uint8_t *data;
	unsigned int len;
}

struct GString {
	char *str;
	size_t len;
	size_t allocated_len;
}

Flexible array members

When working with low-level protocols it's common to encounter variable-length structures consisting of a fixed header followed by a blob of payload bytes. The header contains enough info to identify the layout of the payload, which can then be parsed with content-specific logic.

    byte
+----------+--------+--------+--------+--------+
|   [0..4) |      length (little-endian)       |
+----------+--------+--------+--------+--------+
|   [4..6) | request id (LE) |
+----------+--------+--------+
|        6 | opcode |
+----------+--------+
|        7 | flags  |
+----------+--------+--------+--------+--------+
| [8, ...) |               data                |
+----------+--------+--------+--------+--------+

Pointers to the buffer only need to contain the address of the first byte, because the buffer itself contains the length. This allows functions to have fewer parameters, improving performance due to reduced stack spills.

/* Parameters fit in registers on x86_64 with System V calling convention */
void packet_tee(
	  struct TeeOptions *options
	, struct Packet *packet
	, uint8_t *out_a, size_t out_a_len
	, uint8_t *out_b, size_t out_b_len
);

Traditionally this sort of layout would be implemented by placing a placeholder array at the end of a struct, either of length 0 or length 1. Examples exist from many long-lived codebases, including both Windows and Linux.

/* https://source.winehq.org/git/wine.git/blob/wine-9.10:/include/winnt.h */
#define ANYSIZE_ARRAY   1
typedef struct _TOKEN_GROUPS {
    DWORD GroupCount;
    SID_AND_ATTRIBUTES Groups[ANYSIZE_ARRAY];
} TOKEN_GROUPS, *PTOKEN_GROUPS;

/* https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/uapi/linux/inotify.h?h=v5.6 */
struct inotify_event {
	__s32   wd;             /* watch descriptor */
	__u32   mask;           /* watch mask */
	__u32   cookie;         /* cookie to synchronize two events */
	__u32   len;            /* length (including nulls) of name */
	char    name[0];        /* stub for possible name */
};

/* https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/uapi/linux/soundcard.h?h=v5.6 */
struct sysex_info {
	short key;              /* Use SYSEX_PATCH or MAUI_PATCH here */
#define SYSEX_PATCH	_PATCHKEY(0x05)
#define MAUI_PATCH	_PATCHKEY(0x06)
	short device_no;        /* Synthesizer number */
	int len;                /* Size of the sysex data in bytes */
	unsigned char data[1];  /* Sysex data starts here */
};

This idiom was so widespread that C99 incorporated it into the language as "flexible array members", which uses a slightly different syntax to differentiate from the case of an actual fixed-size array.

As a special case, the last element of a structure with more than one named member may have an incomplete array type; this is called a flexible array member. [...] when a . (or ->) operator has a left operand that is (a pointer to) a structure with a flexible array member and the right operand names that member, it behaves as if that member were replaced with the longest array (with the same element type) that would not make the structure larger than the object being accessed;

The Linux kernel has been migrating to C99 flexible array members over time.

/* https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/uapi/linux/inotify.h?h=v6.9 */
struct inotify_event {
	__s32   wd;             /* watch descriptor */
	__u32   mask;           /* watch mask */
	__u32   cookie;         /* cookie to synchronize two events */
	__u32   len;            /* length (including nulls) of name */
	char    name[];         /* stub for possible name */
};

Pointers to incomplete types

C permits structures to be declared without being defined, which is widely used to reduce transitive includes of header files. If the header never defines the struct then it is an "incomplete type" – pointers to incomplete types may be used like any other pointer, but the type itself (or any value of that type) cannot be inspected. Incomplete types are frequently used by C programmers to exclude implementation details from the public API.

struct SomeStruct;

struct SomeStruct *some_struct_new();
void some_struct_free(struct SomeStruct *);

An interesting consequence of incomplete types is that the pointers don't have to actually point to anything. C programmers are used to thinking of pointers and integers as basically interchangeable[0], and many extant C libraries will do things like stuff metadata into the low bits of an aligned pointer[1].

Slices and strings

Where C has dynamically-sized arrays and NUL-terminated strings, Rust has the slice and str types. Pointers to these types are an (address, size) tuple, making it impossible to accidentally lose track of how large any particular value is.

This also extends to values that contain a slice or string. The Rust equivalent to C's flexible array members uses roughly the same syntax, but the pointers to such a type will contain the size of the dynamically-sized field. A Rust binding to the Linux kernel's inotify API might contain code like this:

use core::ffi::c_char;

// A `*const InotifyEvent` will be twice the size of a `*const ()`, due
// to storing the length of `name`.
struct InotifyEvent {
	wd: i32,        // watch descriptor
	mask: u32,      // watch mask
	cookie: u32,    // cookie to synchronize two events
	len: u32,       // length (including nulls) of name
	name: [c_char], // stub for possible name
}

Note that the length in a *const InotifyEvent pointer is redundant with the length in the InotifyEvent::len field – that redundancy is what this page is intended to identify a solution for.

External types

Rust programmers that want to write bindings to C APIs that use incomplete types as opaque handles found themselves with a problem. Rust doesn't have the concept of an incomplete type, which means there's no good way to declare external FFI functions with type-safe pointer types.

extern "C" {
    fn some_struct_new() -> *mut SomeStruct;
    fn some_struct_free(_: *mut SomeStruct);
}

// In C this is a forward declaration, but in Rust this is declaring a
// statically-sized empty structure.
//
// SomeStruct would implement `Sized`, and thus could be (erroneously)
// passed directly as a function parameter, used as an array item type, etc.
struct SomeStruct;

// This definition of `SomeStruct` wouldn't implement Sized, but because
// Rust uses thick pointers for dynamically-sized types the `extern`
// function declarations would have the wrong ABI.
struct SomeStruct {
	_opaque: [u8],
}

// An uninhabited enum implies that `*const SomeStruct` will never point
// to a valid value, which in turn implies that creating a `&SomeStruct`
// reference is undefined behavior.
enum SomeStruct {}

One proposed solution to this is RFC 1861, which allows declaring external types. These types do double-duty as both incomplete types and flexible array members[3].

#![feature(extern_types)]
extern "C" {
	type SomeStruct;
	type FlexibleArrayU8;
}

// These function declarations have the correct ABI.
extern "C" {
    fn some_struct_new() -> *mut SomeStruct;
    fn some_struct_free(_: *mut SomeStruct);
}

// `HasFlexibleArray` is `!Sized` and `*const HasFlexibleArray` is a thin pointer.
struct HasFlexibleArray {
	len: u32,
	data: FlexibleArrayU8,
}

Unfortunately, combining these properties into a single feature has lead to conflicts when the semantics of C's incomplete types and flexible array members diverge. For example, an incomplete type doesn't have a known alignment[4], which means that it's incoherent for a reference to an extern type to exist.

// This is fine as long as the flexible array member really is a `[u8]`.
fn align_of_HasFlexibleArray(x: &HasFlexibleArray) {
	println!("static alignment: {}", core::mem::align_of::<InotifyEvent>());
	println!("dynamic alignment: {}", core::mem::align_of_val(x));
}

// What should this function print?
fn align_of_SomeStruct(x: &SomeStruct) {
	println!("alignment: {}", core::mem::align_of_val(x));
}

There are three relatively straightforward solutions to this problem, but they all require decoupling incomplete types from flexible array members.

The first option is to simply forbid extern types from becoming references or struct fields. I say "simply" here because it's easy to describe the goal, but the implications for the language semantics are tricky. It also might just be deferring the solution until later, because core::mem::align_of_val_raw() may stabilize one day, and then that function's behavior when passed a pointer to a value with an extern type would be difficult to specify.

A second option is to introduce a pointer-ish type that isn't actually a pointer. It would be the same size as a pointer and propagate provenance, but couldn't be directly converted to a pointer or reference. The guarantees this type would provide are weaker than actual pointers within the Rust aliasing model, since there's no way to tell what the C library stuffed into its bits. Semantically this might be similar to WebAssembly references, which are similarly opaque.

use core::ffi::Incomplete;
struct SomeStruct;

extern "C" {
    fn some_struct_new() -> Incomplete<SomeStruct>;
    fn some_struct_free(_: Incomplete<SomeStruct>);
}

The final option is to just give up on representing C incomplete types in the Rust language. FFI bindings to libraries that use incomplete types would be required to define their own wrapper types, with whatever semantics make sense for that library's data model. There would no longer be any way to identify SomeStruct within the Rust type system, only the handle type – which, being a pointer, is Sized.

#[repr(transparent)]
struct SomeStructRef { ptr: NonNull<()> }

extern "C" {
    fn some_struct_new() -> SomeStructRef;
    fn some_struct_free(_: SomeStructRef);
}

Whatever the future of extern types looks likes, my hope is that decoupling them from unsized thin pointers will improve the roadmap clarity for both features.

Interactions with Mutex and Box

Originally I was unsure whether a thin-pointer DST should have an immutable size. One could imagine, for example, a buffer that could be used to assemble an IP packet by incrementally appending data to the payload. However, discussion on the RFC revealed that the proposed new behavior would only be compatible with existing semantics if the reported size was the same during the entire lifetime of the object.

The first case to consider is Box, which can store unsized values (e.g. Box<[u8]>). When the Box is dropped the value's size is used to construct a Layout for deallocation. If the size of a Packet could change then Box<Packet> would be unsound, and introducing a new ?Trait bound to signify values with immutable sizes is impractical for numerous reasons.

Secondly, it is possible to call size_of_val() on a &Mutex. If the size of a value within a Mutex can change then it would be unsafe to compute its value without holding the lock, which implies size_of_val might deadlock or panic.

Thus, one of the safety preconditions for ThinUnsized must be that the reported size does not change during the value's lifetime.