Impossible requirement in Rust

[ThoBo]

Dear Crustaceans, I am doing a no_std, real time constrained embedded project, and I came across the following problem which is still unsolved for me.

Is it possible in Rust to have a thread safe, recursive struct with Interior Mutability and without using the heap?

Would anyone be able to help me answer this? I have wrecked my head trying to figure this out, and I could not find any solution.

• Must be thread-safe so it cannot have Rc or RefCell
• Must have interior mutability so simply using lifetimes won't work. (I think so at least, I'm not a Rust master yet)
• Cannot use heap which disallows the use of Arc and Box.

How can the indirection caused by the structs’ recursion be avoided?
And how can this all be done without using unsafe code? Is this even possible?

Thanks in advance!

[jendrikw]

If I understand correctly, you want a stack-allocated single-linked list?

You'd be limited to references which reference stack-allocated values. See here: The Stack-Allocated Linked List - Learning Rust With Entirely Too Many Linked Lists

You may be able to use a stack-allocated vector-like type (from heapless or smallvec or similiar).

But isn't this a problem in other languages (specifically C and C++) as well? If you have a working solution (or design) in another language, we can help you translate it to rust.

[chrefr]

Interior mutability and lifetimes are orthogonal concepts.

Here's an example:

use std::sync::{LockResult, Mutex, MutexGuard};

pub struct RecursiveStackOnly<'a, T> {
    value: Mutex<T>,
    prev: Option<&'a RecursiveStackOnly<'a, T>>,
}

impl<'a, T> RecursiveStackOnly<'a, T> {
    pub const fn head(value: T) -> Self {
        Self {
            value: Mutex::new(value),
            prev: None,
        }
    }
    pub const fn cons(value: T, prev: &'a RecursiveStackOnly<T>) -> Self {
        Self {
            value: Mutex::new(value),
            prev: Some(prev),
        }
    }

    pub fn prev(&self) -> Option<&'a RecursiveStackOnly<'a, T>> {
        self.prev
    }

    pub fn value_lock(&self) -> LockResult<MutexGuard<'_, T>> {
        self.value.lock()
    }
    
    pub fn iter(&'a self) -> impl Iterator<Item = &'a RecursiveStackOnly<'a, T>> {
        std::iter::successors(Some(self), |v| v.prev)
    }
}

fn main() {
    let a = RecursiveStackOnly::head(1);
    let b = RecursiveStackOnly::cons(2, &a);
    let c = RecursiveStackOnly::cons(3, &b);

    for item in c.iter() {
        dbg!(*item.value_lock().unwrap());
    }
}

[afetisov]

@ThoBo

Cannot use heap which disallows the use of Arc and Box.

This just means that you need to implement a "heap" manually. Allocate a fixed-size buffer on the stack at runtime or in a properly synchronized static at compile time. Then use an implementation of Box/Arc which use a separate buffer instead of the global heap. The unstable Allocator API is intended for that use case, and all collections support it. However, the Allocator API is still subject to change, so you're probably better off using a custom fork of Box/Arc which implement similar functionality, like bumpalo does. heapless is a popular choice in embedded dev, but I haven't personally worked with it, so can't comment on its subtleties.

Of course, all of the above is valid assuming you have an upper bound on the size of your recursive structure, but you should have it anyway.