Article

Embedded Rust pattern - Zero Sized References

Published on 17 min read

    "Zero Sized Reference" (ZSR) sounds like an impossible thing given that mem::size_of returns a non-zero value for references to Zero Sized Types (ZST) like &() but ZSRs can in fact be constructed and they can improve both the performance and correctness of your embedded application.

    In this post, we'll introduce you to this pattern which is actually used in many embedded crates – though many developers may not have given the actual pattern much attention.

    Let's start by motivating the need for zero sized references.

    Automatic deallocation for memory pools

    Some embedded applications are simple enough that a memory pool that manages memory blocks of the same size (e.g. 128 bytes) – instead of a full blown general-purpose memory allocator – is sufficient to satisfy their dynamic memory management needs.

    The heapless crate provides a lock-free memory pool for such cases. The core of the Pool API is shown below:

    // module: heapless::pool
    
    /// Lock-free memory pool that manages blocks of the same
    /// size (`size_of::<T>`)
    pub struct Pool<T> { /* .. */ }
    
    /// An owning pointer into a block managed by `Pool<T>`
    pub struct Box<T> { data: NonNull<Node<T>> }
    
    /// LIFO linked list (AKA stack) node
    struct Node<T> { /* .. */ }
    
    impl<T> Pool<T> {
        /// Creates an empty memory pool
        pub const fn empty() -> Self { /* .. */ }
    
        /// Returns `None` when the pool is observed as exhausted
        // (if you are wondering why there's no lifetime relationship
        //  between `self` and the returned value, that's because
        //  `Pool` manages "statically allocated" (`&'static mut`)
        //  memory)
        pub fn alloc(&self) -> Option<Box<T>> { /* .. */ }
    
        /// Returns the memory `block` to the pool
        pub fn dealloc(&self, block: Box<T>) { /* .. */ }
    
        // omitted: API to give an initial chunk of memory the pool
    }
    

    One thing that's notably missing is that Box<T> does not implement the Drop trait. This means a block is not automatically returned to the memory pool when it goes out of scope.

    static P: Pool<[u8; 128]> = Pool::empty();
    
    fn main() {
        let x = P.alloc().expect("OOM");
        // do stuff with `x`
    
        // oops, this leaks memory -- the memory block is gone forever
        drop(x);
    
        // to avoid leaking memory you have to call this:
        // P.dealloc(x);
    }
    

    Let's try to fix that!

    Implementing Drop

    One may come up with this solution:

    pub struct Box<T> {
        data: NonNull<Node<T>>,
        // added this ...
        pool: &'static Pool<T>,
    }
    
    impl<T> Pool<T> {
        // omitted: empty, alloc and dealloc methods
    
        // ... and this ...
        unsafe fn dealloc_raw(&self, p: NonNull<Node<T>>) { /* .. */ }
    }
    
    // ... so we can implement this
    impl<T> Drop for Box<T> {
       fn drop(&mut self) {
           unsafe {
              // run T's destructor
              ptr::drop_in_place(self.data.as_ptr());
    
              // dealloc memory block
              self.pool.dealloc_raw(self.data);
           }
       }
    }
    

    This gets the job done: Boxes will be returned to their Pool when they go out of scope. But, this solution also doubles the size of pool::Box<T> (e.g. from 4B to 8B on a 32-bit architecture like ARMv7-M) which is going to regress the performance of moving Boxes around.

    If doubling the size of Box doesn't sound like a big issue to you I shall tell you that most error handling libraries go out of their way (even tapping into the unsafe arts) to make their Error type a thin pointer, instead of a fat pointer (e.g. Box<dyn std::error::Error>), because the perf gains are significant.

    Going back to the task at hand: can we implement Drop without increasing the size of Box? Yes!

    Why use references when you can use ZST?!

    We can actually keep the two-field Box implementation from last section and simply shrink the pool field from 4 (or 8) bytes to 0 bytes by using a Zero Sized Type instead of a reference. We'll need to introduce a Pool trait into the mix to make things work out. Here's the revised version:

    // module: heapless::pool
    
    // put the revised API in a new module
    pub mod singleton {
        /// A memory pool
        pub trait Pool {
            // the type of the memory block managed by this pool
            type Data;
            // ^ this is the `T` in the original `Box<T>` version
    
            /* Public API */
            fn alloc() -> Option<Box<Self>>;
    
            /* Implementation details */
            #[doc(hidden)]
            unsafe fn __dealloc_raw(p: NonNull<Node<Self::Data>>);
        }
    
        pub struct Box<P: Pool> {
            data: NonNull<Node<P::Data>>,
            _pool: PhantomData<P>, // zero sized type, not a reference
        }
    
        impl<P: Pool> Drop for Box<P> {
            fn drop(&mut self) {
                unsafe {
                    ptr::drop_in_place(self.data.as_ptr());
                    // NOTE static method call: no receiver (`&self`)
                    P::__dealloc_raw(self.data);
                }
            }
        }
    }
    
    // the original `Pool<T>` + `Box<T>` implementation still lives here
    

    This may compile but how does one even use this new API? How do you implement the Pool trait? The answer is: you don't implement the Pool trait yourself; you use the pool! macro provided by the heapless crate:

    pool!(P: [u8; 128]);
    
    fn main() {
        // note that `alloc` is a static method (no receiver: `&self`)
        let x: Box<P> = P::alloc().expect("OOM");
        //         ^ NOTE `P`, not `[u8; 128]`
        // do stuff with `x`
        drop(x); // <- this returns the memory block to the pool :tada:
    }
    

    The pool! macro will expand to something like this:

    // expansion of pool!(P: [u8; 128]);
    
    use heapless::pool;
    
    pub struct P; // <- the memory pool is a unit struct
    
    impl pool::singleton::Pool for P {
        type Data = [u8; 128];
    
        fn alloc() -> Option<Box<P>> {
            // ommited: conversion from `pool::Box` to
            // `pool::singleton::Box`
            P::__impl().alloc().map(/* something */)
        }
    
        unsafe fn __dealloc_raw(p: NonNull<Node<[u8; 128]>>) {
            P::__impl().__dealloc_raw(p)
        }
    }
    
    impl P {
        fn __impl() -> &'static pool::Pool {
            static POOL: pool::Pool = pool::Pool::empty();
            &POOL
        }
    }
    

    Singleton-ish

    What the pool! macro is actually doing is creating some sort of global singleton where all instances of, for example, P are handles to the same static variable POOL, which is hidden from the user. In other words, P is a Zero Sized version of a &'static Pool Reference that points into the hidden POOL variable.

    That's the basic idea around Zero Sized References (ZSR): a zero sized proxy type that's equivalent to a shared (&'static) reference. ZSRs come in different flavors: pool! creates ZSR of the "shared" kind (&'static T) but there's also an "owned" variant which we'll look into later.

    But first, let's look into the properties of the pool! abstraction.

    Different types, same interface

    In your embedded application you may end up using different memory pools, each one associated to a different part of your HAL like the radio interface or the USB interface. Some of these memory pools may end up managing memory blocks of the same size. If you are using the non-pool! version of Pool you may end up in a situation where it's not obvious to which pool you should return a memory block. See below:

    // two pools that manage blocks of the same size
    static A: Pool<[u8; 128]> = Pool::empty();
    static B: Pool<[u8; 128]> = Pool::empty();
    
    fn do_stuff(boxed: Box<[u8; 128]>) {
        // ..
    
        // which one to call?
        A.dealloc(boxed);
        B.dealloc(boxed);
    }
    

    The boxed argument could come from either pool A or B. If you pick A.dealloc above you may end up exhausting pool B (all of B's blocks get transferred to pool A); if you pick B.dealloc you may exhaust pool A.

    With the pool! version it's simply not possible to return a memory block to the wrong pool because boxes that belong to a pool are uniquely typed. Each pool! invocation creates a new static variable and gives that static variable a different type. See below:

    pool!(A: [u8; 128]);
    pool!(B: [u8; 128]);
    
    fn do_stuff(boxed: Box<A>) { // <- box managed by pool A
        // ..
    
        // `dealloc` is not a method of a `Pool` trait
        // but if it were this would be rejected at compile time
        B::dealloc(boxed); //~ error: expected type `B`; found type `A`
    }
    

    Even though both pools, A and B, are proxies to static variables with the same type Pool<[u8; 128]> each pool is exposed to the user as a different type. This lets you track in the type system the association between a memory block and a pool.

    If for some reason you need to write function that must work with boxes managed by different pools you can write generic code:

    // generic function ...
    fn zero_before_dealloc<P, T>(boxed: Box<P>)
    where
        P: Pool<Data = T>
        T: Zeroable, // unsafe marker: implies no destructor, etc.
    {
        let p: NonNull<Node<T>> = Box::into_raw(boxed);
        // zeroes the block, even in presence of compiler optimizations
        T::zero(p);
        unsafe {
            P::dealloc_raw(p); // return it to the pool
        }
    }
    
    fn discard(a: Box<A>, b: Box<B>) {
        // ... that works with boxes from pool A and B
        zero_before_dealloc(a);
        zero_before_dealloc(b);
    }
    

    Zero Sized "Owned" References

    The pool! macro creates a static variable proxy with global (static variable like) visibility but this not a strict requirement of the ZSR pattern. Here we present an "owned" variant that does not have global visibility:

    /* Public API */
    pub struct Proxy { // NOTE Zero Sized Type
        _marker: PhantomData<&'static mut Impl>,
    }
    
    impl Proxy {
        /// Returns the `Some` variant only once
        pub fn claim() -> Option<Proxy> {
            static CLAIMED: AtomicBool = AtomicBool::new(false);
    
            if CLAIMED
                .compare_exchange(false, true, SeqCst, SeqCst)
                .is_ok()
            {
                // not yet claimed
                // NOTE(unsafe) this branch is executed at most once
    
                unsafe { Self::__impl().write(Impl::new()) }
    
                // do not move the previous 'write' beyond this fence
                atomic::compiler_fence(SeqCst);
    
                Some(Self { _marker: PhantomData })
            } else {
                // already claimed
                None
            }
        }
    
        /// Frobs `arg`
        pub fn frob(&mut self, arg: SomeArg) {
            (*self.__impl()).frob(arg)
        }
    
        /* Implementation detail */
        fn __impl() -> *mut Impl {
            static mut IMPL: MaybeUninit<Impl> = MaybeUninit::uninit();
            unsafe { IMPL.as_mut_ptr() }
        }
    }
    
    /* Private API */
    struct Impl { /* data */ }
    
    impl Impl {
        // NOTE constructor does not need to be `const`
        fn new() -> Self { /* .. */ }
        fn frob(&mut self, arg: SomeArg) { /* .. */ }
    }
    

    Usage looks like this:

    fn main() {
        // before claim: `IMPL` static variable is *un*initialized
        let mut proxy = Proxy::claim().expect("already claimed");
        // after claim: `IMPL` static variable is initialized
    
        // further calls to `claim` (from any thread) will return None
        assert!(Proxy::claim().is_none());
    
        // all methods will operate on an initialized static variable
        proxy.frob(SomeArg);
    }
    

    Proxy is a Zero Sized Reference that behaves like a normal variable and it's subject to the usual ownership semantics. We say this is an "owned" variant because Proxy is equivalent to a mutable reference with static lifetime (&'static mut T), which has the same move semantics as alloc::Box<T>.

    So, where would you use this "owned" variant?

    Spotted in the wild: MMIO registers

    This "owned" variant of the ZSR pattern is widely used in the embedded Rust ecosystem. The API generated by svd2rust uses this pattern to:

    • make references to registers zero sized, for the same perf reasons as wanting to keep pool::Box pointer sized.

    • to let you control access to peripherals via ownership, which gives you better encapsulation than C where peripherals can be accessed from pretty much anywhere.

    For reference, the svd2rust API as of version 0.17.0 looks like this:

    #![no_std]
    
    fn main() {
        // `take` is the same as `claim`: it returns
        // the `Some` variant only once
        let peripherals = nrf51::Peripherals::take().expect("already claimed");
        //                ^^^^^ Peripheral Access Crate (PAC)
        //                      generated by svd2rust
    
        // "the GPIO peripheral"
        // this handle grants exclusive access to the peripheral
        let gpio = peripherals.GPIO;
    }
    

    Unlike the general version of claim, Peripherals::take performs no initialization of static variables. These Zero Sized References are not pointing into static variables (RAM) but into Memory Mapped I/O registers (which have known addresses).

    In recent work: filesystems

    Recently, we came up with a Filesystem API based on the ZSR pattern for our friends at Iqlusion who are building armistice – a hardware private key storage for next-generation cryptography – as part of the development of a Hardware Abstraction Layer for the USB Armory Mk II development board.

    We used the Zero Sized References pattern to implement "close on drop" semantics for files without storing a pointer to its filesystem in the file handle.

    Like with memory pools you'll want a trait (Filesystem) that provides a common interface to different filesystem types.

    /// NOTE do NOT implement this yourself;
    /// use the `filesystem!` macro
    pub unsafe trait Filesystem: Copy {
        /// Where does the filesystem live? RAM? on-chip FLASH?
        type StorageDevice: Storage;
        //                  ^^^^^^^
        // interface between the FS and the storage device
    
        /* Public API */
        fn mount(
            storage: Self::StorageDevice,
            format_before_mounting: bool,
        ) -> io::Result<Self>;
    
        /* Implementation details */
        #[doc(hidden)]
        unsafe fn __close_in_place(
            &self,
            f: &mut File<Self>, // not consumed by the method
        ) -> io::Result<()>;
    }
    
    /// A handle to an open file that lives in filesystem `FS`
    pub struct File<FS: Filesystem> {
        // omitted fields: state, buffers, caches, etc.
        fs: FS, // Zero Sized Reference to the filesystem
    }
    
    impl<FS: Filesystem> File<FS> {
        /// NOTE must present a handle to the FS to "prove"
        /// it has been mounted
        pub fn create(
            fs: FS,
            path: impl AsRef<Path>,
        ) -> io::Result<Self> {
            // ..
        }
    
        pub fn write_all(
            &mut self,
            data: &[u8],
        ) -> io::Result<()> { /* .. */ }
    
        pub fn close(self) -> io::Result<()> { /* .. */ }
    }
    
    /// NOTE this panics if I/O errors occur while closing the file.
    /// Use the `File.close` method, which returns a `Result`, to
    /// handle those I/O errors
    impl<FS: Filesystem> Drop for File<FS> {
        fn drop(&mut self)  {
            let fs = self.fs; // make a copy
            fs.close_in_place(&mut self).expect("I/O error");
            // omitted: deallocate buffers
        }
    }
    

    You would use the API like this:

    filesystem!(F, StorageDevice = uSD);
    
    // get handle to micro SD card subsystem
    let usd = uSD::claim()?;
    let format = true;
    let fs = F::mount(usd, format)?;
    
    let mut f: File<F> = File::create(fs, "foo.txt")?;
    f.write_all(b"Hello, file!")?;
    
    // file will be closed automatically at the end of the scope
    // (implicit `drop`)
    // drop(f);
    
    // OR you can close the file manually to handle errors
    f.close()?;
    

    Note how the API also prevents operations like "creating a file on a filesystem that has not yet been mounted" at compile time: File::create requires a handle to the filesystem and that handle can only exist after the filesystem has been mount-ed.

    If you use the filesystem! macro to create one more filesystem, say backed by RAM (so tmpfs like), then that filesystem gets its own type, let's say R. All files include the filesystem they belong to in their type so File<F> lives in FS F whereas File<R> lives in FS R. Having different types means that you can avoid, at compile time, operations like closing (committing) a file to the wrong filesystem:

    filesystem!(F, StorageDevice = uSD); // non-volatile storage
    filesystem!(R, StorageDevice = RAM); // volatile storage
    // ..
    
    let r = F::mount(usd, format)?;
    let f = R::mount(ram_block, format)?;
    
    let mut file: File<R> = File::create(fs, "foo.txt")?;
    file.write_all(b"Hello, file!")?;
    
    // wrong filesystem!
    F::close(file)?; //~ error: expected type `F`; found type `R`
    

    This Filesystem implementation uses the littlefs C library under the hood to do the bulk of the work. Creating a safe Rust wrapper around that C library proved rather challenging – and probably deserves its own blog post – but at the end of the day Rust features let us defuse the traps in the C API so that consumers of the Rust wrapper won't run into them.

    Food for thought: capabilities

    If you are writing single-process embedded applications the above Filesystem API lets you restrict, at compile time, which parts of your application can use the FS.

    Consider the following functions. You can tell which ones use the filesystem, and which filesystem, by just looking at their signatures. Or, in other words, the function signatures reflect the capabilities of the subroutine.

    // filesystem stored in internal (on-chip) Flash memory
    filesystem!(Internal, StorageDevice = FLASH);
    
    // filesystem stored in external (on-board) SPI-NOR Flash
    filesystem!(External, StorageDevice = SPI_NOR);
    
    // can use either filesystem
    fn create_lockfile(f: impl Filesystem) -> io::Result<(), ()> {
        // ..
    }
    
    fn uses_the_internal_fs(f: Internal) -> io::Result<(), ()> {
        // ..
    }
    
    fn uses_the_external_fs(f: External) -> io::Result<(), ()> {
        // ..
    }
    
    fn cannot_use_any_fs(/* because no arguments */) { /* .. */ }
    

    If you are structuring your embedded application as a set of tasks, either async tasks or reactive tasks, you can similarly control the capabilities of each task by moving, or not, a Filesystem handle into the task. With async tasks that may look like this:

    #![no_std]
    
    fn main() -> ! {
        let fs = Filesystem::mount(/* .. */);
    
        // tasks
        let first = uses_the_fs(fs);
        let second = cannot_use_the_fs();
    
        // run asynchronous tasks concurrently
        executor::run!(first, second)
    }
    
    async fn uses_the_fs(fs: Fs) -> ! { /* .. */ }
    
    async fn cannot_use_the_fs() -> ! { /* .. */ }
    

    If we had opted for a globally available fs API, like the one provided in the Rust standard library, it would be much harder to identify which parts of the application may perform FS operations.

    Conclusion

    This is one of the patterns we use to build correct-by-construction software for our clients. In this post we have covered some of the possible uses of this pattern but, for brevity, have left out (important) details like the concurrency (thread / interrupt) safety of the ZSR proxies and the extra mileage you can get out of the runs once section in the ZSR::claim constructor. Still, we hope that the post motivates you into trying out this pattern in your embedded code!


    Ferrous Systems is a Rust consultancy based in Berlin. Need to strengthen your Rust Project with the external development support? Looking for the advise on how to get the best out of Rust features? Get in touch with us! Want to get up to speed with the language and its tooling? We also offer remote training on basic Rust, advanced topics and embedded Rust — to receive our updated training program, subsribe to our newsletter.