Rust wrapper around C flexible array

I'm trying to create Rust bindings for a C API that uses a "flexible array".

typedef struct Buffer {
    uint32_t metadata;
    void *data;
} Buffer;

typedef struct BufferList {
    uint32_t num_buffers;
    Buffer buffers[1]; // <--- could be >= 1 in reality
} BufferList;

I need to accommodate both of these use cases:

  1. Rust processing of a BufferList allocated in C
  2. C processing of a BufferList allocated in Rust

What I've come up with is to make the Rust version of BufferList a struct without any public members, where instead of accessing num_buffers and buffers members directly, the user calls associated functions which perform some unsafe manipulations.

#![allow(unused)]

use std::ffi::c_void;
use std::mem;

#[repr(C)]
pub struct Buffer {
    pub metadata: u32,
    pub data: *mut c_void,
}

#[repr(C)]
struct BufferListInternal {
    num_buffers: u32,
    buffers: [Buffer; 1],
}

#[repr(transparent)]
#[derive(Copy, Clone)]
struct BufferList {
    inner: *mut BufferListInternal,
}

impl BufferList {
    pub fn new(num_buffers: u32) -> Self {
        let num_buffers = std::cmp::max(num_buffers, 1);
        let offset_of_buffers = mem::align_of::<Buffer>();
        let size = offset_of_buffers + num_buffers as usize * mem::size_of::<Buffer>();
        let mut buffer_list = BufferList {
            inner: Vec::with_capacity(size).as_mut_ptr() as *mut BufferListInternal,
        };
        unsafe {
            (*buffer_list.inner).num_buffers = num_buffers;
        }
        buffer_list
    }

    pub fn num_buffers(&self) -> u32 {
        unsafe { (*self.inner).num_buffers }
    }

    pub fn buffer_mut(&mut self, buffer_num: u32) -> Result<&mut Buffer, String> {
        if buffer_num < unsafe { (*self.inner).num_buffers } {
            Ok(unsafe {
                let buffers: *mut Buffer = &mut (*self.inner).buffers as *mut _ as *mut Buffer;
                &mut *(buffers.add(buffer_num as usize))
            })
        } else {
            Err("buffer index too large".to_string())
        }
    }
}

#[test]
fn buffer_list_allow_deep_access() {
    let mut buffer_list = BufferList::new(3);
    assert_eq!(buffer_list.num_buffers(), 3);
    let mut buffer = buffer_list.buffer_mut(0).unwrap();
    buffer.metadata = 42;
    assert_eq!(unsafe { (*buffer_list.inner).buffers[0].metadata }, 42);
}

#[test]
fn buffer_list_c_abi() {
    let mut buffer_list = BufferList::new(3);
    assert_eq!(num_buffers_from_c(buffer_list.inner), 3);
    
    // This is what I want, but it doesn't work because of the extra
    // layer of indirection in the Rust version of BufferList.
    //assert_eq!(num_buffers_from_c(&buffer_list), 3);
}

extern "C" fn num_buffers_from_c(pointer: *const BufferListInternal) -> u32 {
    unsafe { (*pointer).num_buffers }
}

(Playground)

However, I'm dissatisfied about borrowing behavior: &buffer_list and &mut buffer_list won't behave as Rust users might expect because of the extra level of indirection.

Thoughts?

First of all, your code has triggered Miri, a Rust interpreter designed to detect as much UB as possible:

  • You can run Miri, in the Playground, by having an fn main() and using the Tools on the top-right menu.

I will thus go over fixing your code, but keep in mind that flexible array buffers don't play well with Rust semantics, and this kind of "extra indirection" (which in practice can be softened by marking the functions #[inline], or by defining your own types for the shared ref and exclusive ref types (the former being Copy, the latter offering a .reborrow() method; the ergonomics are then not great)) is thus often unavoidable.

Buffer is quite straight-forward to define:

#[repr(C)]
struct Buffer {
    metadata: u32,
    data: *mut c_void,
}

BufferList is indeed quite trickier. You cannot use a fixed length (one that may be too short or too long) while also using "high-level Rust pointers" (&, &mut, Box, etc.) to such Buffer.

From having had to deal with those in the pasts, there are two approaches:

  • define BufferList as a DST (dynamically sized-type):

    #[repr(C)] // guarantees ordering, but does not really have a meaning in C
    struct BufferList {
        num_buffers: u32,
        buffers: [Buffer],
    }
    

    the complication then comes from creating a high-level Rust pointer to that, which will be a fat pointer, i.e., a 2-pointer-wide pair / struct with the address of the first elem (if any), and the elem count (yes, that will be redundant, but that's the price to pay, currently, with high-level Rust pointers to DSTs).

  • Never expose BufferList itself to Rust code as an arbitrary pointee, but rather create your own newtype representing a slim implementation of a type with Box<BufferList> semantics. This is what you have done, and good job with going in that direction, not everybody does it (they go with the first approach with a fake fixed length, which is UB). Sadly you got the implementation wrong, but we'll now see how to handle that part.

The "Box<BufferList>" newtype w/ hand-rolled implementation

In your implementation, the pointee is now called BufferListInternal, and that newtype wrapper over an owning pointer is BufferList.

The offset_of_buffers is a bit of a shortcut that doesn't generalize very well; you are relying on size_of::<u32>() (metadata field) being smaller or equal than the alignment of BufferListInternal (otherwise that computation of the offset is wrong). This is true in your case, but it'd warrant some comment.

This is the part where all hell breaks loose :sweat_smile::

  • you don't type-annotate the construction of the Vec, so subtle inference changes could change the semantics in very wrong ways. Here, for instance, the fact that this compiles, means that inference did lead to a single candidate type, which given the pointer cast, must have been a BufferListInternal. The MIR output (available in the top-left menu of the Playground) confirms this:

    This means that we are heap-allocating an uninitialized buffer of size(in bytes) BufferListInternals elements, thus having a size, in bytes, of size * size_of::<BufferListInternal>(). "Luckily", this just leads to over-allocating: since the latter is bigger than what you intended, you won't happen to read nor write past the allocation.

  • The second problem comes from destructors and temporaries: by doing Vec::new() / Vec::with_capacity() followed by an .as_mut_ptr() (which borrows the Vec, and yields a lifetime-disconnected (still borrowing) pointer) Rust:

    1. Vec::with_capacity() → It allocates your buffer;

      Since it is not bound to any local variable / name, Rust creates its own temporary that will be dropped at the end of the enclosing statement. In the following diagram, that local is called _15.

    2. Vec::as_mut_ptr() → Rust exclusively borrows the vec ( &mut Vec) to yield a pointer to the buffer owned by the Vec. Same as before, it uses its own temporary to hold the obtained pointer (called _13).

    3. It then writes that obtained pointer in the .inner field (.0) of the to-be-returned value (_0, of type BufferList).

    4. This marks the end of the aforementioned enclosing statement, at which point Rust cleans up its temporaries, leading to the Vec temporary (_15) being drop-ped! This deallocates the just allocated buffer, which means that the .inner pointer dangles as soon as it is created! If this had been a regular borrow, Rust would have errored about a "local does not live long enough" error, but given the lifetime-erased nature of the obtained pointer, Rust no longer knows that such pointer is borrowing from a deallocated Vec, and thus says nothing. This is the same problem as in CString/.as_ptr() is incredibly unsafe :(.

    Hence the UB detected by MIRI.

The "cleanest" (imho) way to write this pattern

The correct way of writing that function is by relying heavily on Layout and its convenience methods, as well as the following very handy type definition:

#[repr(C)] // required for the alloc layout shenanigans!
struct BufferList<
    Buffers // make the Rust type generic over its trailing field
    : ?Sized  // with support for DSTs (here, mainly, `[Buffer]`)
    = [Buffer] // add a convenient default parameter
>
{
    num_buffers: u32,
    buffers: Buffers,
}

This way BufferList, with no params provided, represents the type with a [Buffer] field I was talking about at the beginning of my post.

You can already see how convenient this def is, when you see you can write:

let boxed_buffer_list: Box<BufferList> = Box::new(BufferList {
    num_buffers: 2,
    buffers: [ Buffer { … }, Buffer { … }, ], // : [Buffer; 2]
})/* coercion to a fat pointer */;

to which we can already add:

impl<Buffers : ?Sized> BufferList<Buffers> {
    pub
    fn as_ptr (self: &'_ Self)
      -> *const BufferList<[Buffer; 1]>
    {
        self
            as *const Self // remove the lifetime and the "higher-level-ness" (still a fat pointer)
            as *const _ // slim pointer (trash away the len part of the fat pointer)
    }

    pub
    fn as_mut_ptr (self: &'_ mut Self)
      -> *mut BufferList<[Buffer; 1]>
    {
        self as *mut Self as *mut _
    }
}

This will enable you to use this type across FFI.

With the very near-future min_const_generics, we will be able to add a stack / inline constructor:

impl<const N: usize> BufferList<[Buffer; N]> {
    pub
    fn new (buffers: [Buffer; N])
      -> Self
    {
        Self {
            num_buffers: N.try_into().expect("Count overflowed `u32`"),
            buffers,
       }
    }

    // Heap-allocate and then fatten the obtained pointer
    pub
    fn boxed (self: Self)
      -> Box<BufferList /* <[Buffer]> */>
    {
        Box::new(self)
    }
}

And now, for the runtime length initialization using heap allocation, as you attempted to do:

extern crate alloc as alloc_crate;

use ::core::{
    convert::{TryFrom, TryInto},
    ptr,
};
use ::alloc_crate::alloc::{self, Layout};

impl BufferList {
    pub
    fn new (iterator: impl ExactSizeIterator<Item = Buffer>)
      -> Box<Self>
    { unsafe {
        let count = iterator.len();
        let count_u32 = u32::try_from(count).expect("Count overflowed `u32`");
        // layout for the `num_buffers` field + padding for the `buffers`.
        let num_buffers_layout = Layout::new::<BufferList<[Buffer; 0]>>();
        let buffers_layout = Layout::array::<Buffer>(count).unwrap();
        let (self_layout, buffers_offset) =
            num_buffers_layout.extend(buffers_layout).unwrap()
        ;
        let self_layout = self_layout.pad_to_align(); // in case `num_buffers_layout` had a higher alignment than that of `Buffer`.
        let ptr = alloc::alloc(self_layout).cast::<u8>();
        if ptr.is_null() {
            enum Diverged {}
            let _: Diverged = alloc::handle_alloc_error(self_layout);
        }
        let (ptr_to_num_buffers, mut ptr_to_buffers) = (
            ptr.cast::<u32>(),
            ptr.add(buffers_offset).cast::<Buffer>(),
        );
        ptr_to_num_buffers.write(count_u32);
        // We need to use `zip` as extra safety since
        // `ExactSizeIterator` is allowed to lie (the trait is not `unsafe`).
        let ref mut idxs = 0 .. count;
        idxs.zip(iterator).for_each(|(_, buffer)| {
            // zip prevents the iterator from yielding too many elems
            ptr_to_buffers.write(buffer);
            ptr_to_buffers = ptr_to_buffers.add(1);
        });
        // the iterator may also have yielded not enough elems
        assert!(idxs.next().is_none(), "ExactSizeIterator lied");
        // at this point, we know we have correctly
        // initialized and written everything 🙌
        // Time to fatten our pointer… (redundantly embed the length)
        let fake_fat_ptr: *mut [BufferList<Buffer>] = ptr::slice_from_raw_parts_mut(ptr.cast(), count);
        let actual_fat_ptr: *mut BufferList<[Buffer]> = fake_fat_ptr as _;
        Box::<Self>::from_raw(actual_fat_ptr)
    }}
}
14 Likes

To add to that, even the original C code has undefined behavior. A flexible member should be spelled Buffer buffers[];, and it is only valid in C99 and later standards (the trick presented here is known as "the struct hack" in C89 and it is not a compliant way of realizing flexible array members).

Accessing an array beyond its declared length is UB in all versions of C, even if the allocation extends to the past-the-end elements, because they do not "designate the same object" (as the Standard phrases it).

5 Likes

@Yandros, thank you very much for your tour de force answer. I am researching many aspects and plan to respond to the design recommendations later.

Ugh. I'm extremely unhappy to have left this landmine in the code for you to disarm. I showed this to San Diego Rust at the virtual meetup last night and they jumped on it too.

An earlier iteration used calloc and free:

@@ -27,7 +26,7 @@
         let offset_of_buffers = mem::align_of::<Buffer>();
         let size = offset_of_buffers + num_buffers as usize * mem::size_of::<Buffer>();
         let mut buffer_list = BufferList {
-            inner: Vec::with_capacity(size).as_mut_ptr() as *mut BufferListInternal,
+            inner: unsafe { libc::calloc(size, 1) as *mut BufferListInternal },
         };
         unsafe {
             (*buffer_list.inner).num_buffers = num_buffers;
@@ -51,6 +50,12 @@
     }
 }
 
+impl Drop for BufferList {
+    fn drop(&mut self) {
+        unsafe { libc::free(self.inner as *mut c_void) }
+    }
+}
+

That might be goofy, but it passed Miri (after removing a #[derive(Copy, Clone)] that's incompatible with Drop). Furthermore, because it's not idiomatic Rust, it draws attention to itself as something to review — and it's an appropriate "tell" for my background as a reasonably experienced C programmer but a relative newcomer to Rust.

This misadventure with pointers illustrates why I want to design BufferList to work with &, &mut and friends, in order to spare users from dealing with * mut and * const as much as possible. Technically the unsound code only happens at the site of the pointer dereference, but the "safe" code is where you set yourself up for failure.

As a data point, as I've learned to work with Rust's borrow checker, I've found the distinctions between pointers and references hard to grok: what's actually being passed around underneath, when implicit dereferencing happens automagically and when explicit dereferencing is needed, the difference between &(*pointer) and &{ *pointer }, what the guarantees are for lifetime management. That confusion is how my mistake originated, although there were at least two missed opportunities to avert disaster:

  1. I should have stuck with calloc/free because I was uncertain about using Vec and I knew that I got it wrong, the failure mode would be extremely severe.
  2. At the language level, it's a bummer that it's so easy to create a dangling pointer in safe code that may be very far away from the unsafe block that ultimately performs the dereference. In a perfect world, these as_ptr and as_mut_ptr routines wouldn't be such footguns.

Back in the day, I used to script valgrind checks for my C projects. Since I'll be continuing to work with unsafe, it's clear that I'll need to do something similar while working with Rust, using Miri or other tools.

2 Likes

Heh. I simplified the actual API I'm working with to better isolate the issue of flexible arrays, but here's the original, from Apple's Core Audio API, in the CoreAudioBaseTypes.h header file:

struct AudioBufferList
{
    UInt32      mNumberBuffers;
    AudioBuffer mBuffers[1]; // this is a variable length array of mNumberBuffers elements
	
#if defined(__cplusplus) && defined(CA_STRICT) && CA_STRICT
public:
    AudioBufferList() {}
private:
    //  Copying and assigning a variable length struct is problematic; generate a compile error.
    AudioBufferList(const AudioBufferList&);
    AudioBufferList&    operator=(const AudioBufferList&);
#endif

};

Oh, so it's not code you control – sure, in that case there's not much to do about it.

1 Like

I think it's probably also worth to mention my crate, slice-dst, whose purpose is to make working with FAM types in Rust a bit easier. You can combine it with erasable as well to manage thin pointers in a slightly less adhoc and footgunny method. These crates were originally written (and are used) to optimize the amount of allocation in rust-analyzer's syntax tree representation. (If the rustc/r-a syntax tree merger ever happens, they may end up in rustc's tree! :blush:)

Though at the same time: the version using generics to create the type as sized initially is standard, understood by most rustaceans, and doesn't involve the pile of unsafe that slice-dst requires. (The advantage is slight but there: avoiding generics reduces monomorphization cost.)

5 Likes

Then how would you express getting a mutable pointer to the underlying storage without consuming the Vec? Note the naming scheme also reflects this distinction:

  • as_ means that you're borrowing/viewing the struct as something else, without consuming it (they usually take a &self or &mut self parameter)
  • into_ means that you're converting the struct to something else, consuming it in the process (they usually take a self parameter)
  • from_ means that you're converting something else to this struct, consuming it in the process. This is usually called with the returned value from the into_ variant.

For example for Vec there's as_mut_ptr that doesn't consume, into_raw_parts (unfortunately still unstable) that consumes it and returns the pointer to the underlying storage, the length and the capacity (unitialized elements included), and into_boxed_slice + Box::into_raw combo (this is somewhat hidden, strange and may also reallocate) that gives you a pointer to the underlying storage and the length, however it drops the excess storage; this may reallocate, however you don't need to store the capacity.

3 Likes