Typed scoped "self-referential" arena in safe rust

help
1

Hello! I'm trying to implement scoped append-only typed arena whose types have references to itself. Everything works fine without reusing initial buffer, but I'm having trouble finding a solution that reuses it. The issue looks like standard rust self-referential struct problem but not exactly. Here is the code: Rust Playground

Does anyone know if it is possible?

1 Like
2

Borrow checking can't reason about self-referential types (since they form cycles), so they're forbidden in safe code.

Creation of self-referential types requires unsafe, and there's no correct lifetime annotation for them.

You must also be very careful about anything that can make a &mut reference to self-referential types, even temporarily, because &mut implies exclusivity through its mere existence (even if not dereferenced) and guarantees that there are no other usable references to the same object.

You also need to be careful about running Drop of such types when the arena is torn down. They can use their references while being dropped, but could end up referencing an already-dropped object from the same arena. This is why bumpalo forgets the contents.

2 Likes
3

That’s coming remarkably close to working with only the standard library.

I’m looking for possible crates that could fill the gap… maybe something like this could help that cast_slice method would help your case a lot. Edit: on second look, it seems like its covariance alone can support this use-case, too.[1] Also note that I have never reviewed this crate; but the basic idea of this type seems sound, and the crate has a decent number of users.

  1. another edit: on third look, I seem to have incorrectly deduced covariance, the type is actually invariant in T – rustdoc should really learn to display such things directly ↩︎

4

Edit: Missed “safe” in the title :frowning:

How about something like this:

pub struct Arena<'a, T>(Mutex<IterMut<'a, MaybeUninit<T>>>);

impl<'a, T> Arena<'a, T> {
    pub fn new<U>(buf: &'a mut [MaybeUninit<U>])->Self {
        // Safety: Uninit -> Uninit
        let (_, buf, _) = unsafe { buf.align_to_mut() };
        Arena(Mutex::new(buf.iter_mut()))
    }
    
    pub fn push(&self, val: T)->&'a T {
        let mut lock = self.0.lock().unwrap();
        let entry_mut = lock.next().unwrap();
        entry_mut.write(val)
    }
}
5

Sure, Drop needs some care. But my current demand is actually only for Copy types to implement similar to GPU algorithms like "use some memory for computations during one epoch, and then forget whole data".

So, actually I'm asking about how can we deal with invariance that appears for my example type Data<'t> as @steffahn noted.

6

So it is possible using that crate:

use without_alloc::Uninit;
impl Buffer {
    pub fn new(capacity: usize) -> Self {
        Self(Box::new_uninit_slice(capacity))
    }
    pub fn append_only_scope<F, R>(&mut self, f: F) -> R
    where
        F: for<'s> FnOnce(&AppendOnlyScope<'s>) -> R,
    {
        let boxed_mut: &mut [MaybeUninit<Data<'_>>] = Uninit::from_maybe_uninit_slice(&mut self.0)
            .as_memory()
            .cast_slice()
            .unwrap()
            .into_maybe_uninit_slice();
        f(&AppendOnlyScope {
            entries: Mutex::new(boxed_mut.iter_mut()),
        })
    }
}
1 Like
7

It also allows for

// …

use without_alloc::Uninit;
impl Buffer {
    // …
    pub fn append_only_scope<'s>(&'s mut self) -> AppendOnlyScope<'s> {
        let boxed_mut: &mut [MaybeUninit<Data<'_>>] = Uninit::from_maybe_uninit_slice(&mut self.0)
            .as_memory()
            .cast_slice()
            .unwrap()
            .into_maybe_uninit_slice();
        AppendOnlyScope {
            entries: Mutex::new(boxed_mut.iter_mut()),
        }
    }
}

// …

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_append_only_scope() {
        let mut buffer = Buffer::new(10);
        test_scope(&buffer.append_only_scope());
        test_scope(&buffer.append_only_scope());
    }
    // …
}
2 Likes
8

Yeah, it works, it is so strange. Therefore what are we missing in std? Something like safe transmuting &mut [Data<'static>] into &mut [Data<'_>]? (for real use cases we could ignore MaybeUninit for now because initialization is needed only once)

As you can see in my initial code, I tried to did this kind of transmute by abusing allocation-free vec collect specialization. But invariance didn't let me do this in opposite direction.

Edit: I realized that in fact MaybeUninit is important too to leave everything unitialized for safe rust after another scoped use.

1 Like
9

Yes exactly.

Presumably the standard library might be a bit more hesitant to offer this exact capability because the implementation (at least as is offered with without_alloc) turns a mismatch of layout (size or alignment) into run-time errors, even though for many types, the exact size and alignment is not a stable guarantee.

If only a lifetime changes, it isn't an issue of course as that can't affect the layout.

10

It already has [T]::align_to_mut; I expect that a safe wrapper would have essentially the same shape, but require MaybeUninit for the transmute-flavored parts.

1 Like
11

Oh, I haven't noticed that method got a lot stronger documentation. It used to say things such as

The method may make the middle slice the greatest length possible for a given type and input slice, but only your algorithm’s performance should depend on that, not its correctness. It is permissible for all of the input data to be returned as the prefix or suffix slice.

1 Like
12

I've gone ahead and created std proposal: Safe aligning of `MaybeUninit` mutable slices · Issue #564 · rust-lang/libs-team · GitHub. Let's see what others think.

3 Likes