`guest_cell`: Storage space for externally-owned private data

I just published v0.1.0 of guest_cell, and I'd appreciate any feedback on the API design & implementation.

It's designed to help with visitor-like patterns, where some algorithm needs to store temporary information about values of varying types. Each object to be visited contains a GuestCell<T>, and the visitor uses a Guest to access a private T value.

Each Guest can own values in arbitrarily many GuestCells and each GuestCell provides storage space for arbitrarily many Guests, but each Guest gets only a single slot in each GuestCell.

How do you create a Guest? An example would help a lot.

Instead of a Mutex I would use a DashMap, or at least a RwLock.

If you can change Id to u64, you can use atomics, which are much faster than mutexes.

You can also use a SlotMap instead of a HashMap.

2 Likes

My apologies for the lack of an example; I wrote this as a building block for a software-transactional memory library, where each transactional cell has a GuestCell to hold uncommitted values, and each transaction has a Guest identifying which of those values should be committed together. That's a bit complicated for a GuestCell example, and I haven't yet thought up a simpler use case.

Guest implements Default, which is the only way to create one; I should probably have a new() inherent function that acts as an alias.

SlotMap looks maybe a little problematic here, because I don't have a convenient place to store the generated keys: Each Guest can serve as an owner in an arbitrary set of GuestCells and so would need to keep a collection of keys instead of a single id, as it currently does.

DashMap and RwLock are more plausible, but I'd want to do some benchmarking first: The lock is only held for the duration of a single lookup, insert, or delete operation and then released. In particular, the accesses of looked-up items are not controlled by the Mutex at all-- That aliasing is instead enforced statically. My instinct says that the amount of contention there should be small enough that more complicated access control is likely to cost more than it gains, but I could easily be wrong about that.

Id is designed to be feature-configurable; the only drawback of u64 is a (minimal) possibility of overflow. The code is only sound if no two concurrent UniqueIds are ever the same, which I currently ensure by never reusing an id. This, in turn, means that a long-running program will eventually panic when the space of available ids is exhausted.

2 Likes

It's somewhat dubious to move around the unique Box<T>s in the HashMap while letting guests hold references to their data. I'd suggest storing raw pointers instead, to prevent any issues with pointer invalidation.

2 Likes

Miri seems ok with the general idea, but I agree that it does feel a bit weird. The API ended up simple enough that I should be able to insert from_raw/into_raw at the appropriate places; I avoided that originally in case I accidentally introduced a leak or double-free by missing a necessary call.

Edit: Actually, the derived Debug for GuestCell is currently unsound because of this. It may try to read the contents of one of the Boxes while it's being modified by a Guest :frowning: . Switching to raw pointers in the map will fix it.

Edit 2: I just published v0.1.1, which switches to storing raw pointers and adds Guest::new() as an alias for Guest::default(). I'll need to think about when it's appropriate for GuestCell to be Send and/or Sync.

Looking through the implementation… I’ve lately become wary of thread_local behavior for destructors. The docs sound as if it’s not out of the question that accessing an already dropped thread-local might succeed (implicitly re-initializing it back to its default/initial value, I suppose). It also doesn’t specify the order of descructors.

This could mean… and this would be platform-specific of course… that it’s not completely out of the question that my thread-local destructor could sneek in-between your HI and LO’s destructors.

Relevant code for reference…

impl Default for UniqueId {
    fn default()->Self {
        thread_local! {
            static HI: Cell<IdHi> = Cell::new(0);
            static LO: Cell<IdLo> = Cell::new(IdLo::MAX);
        }

        let lo = LO.with(|prev| prev.get()).wrapping_add(1);
        let hi = match lo {
            0 => next_hi(),
            _ => HI.with(|prev| prev.get())
        };

        LO.with(|prev| prev.set(lo));
        HI.with(|prev| prev.set(hi));

        UniqueId(Id(hi,lo))
    }
}

So if HI is already destructed, and LO isn’t yet, and accessing HI would thus possibly silently reset it back to 0, then a call to this default() method could return an id with hi = 0, lo = …whatever-the-current-lo…, which is of course no longer guaranteed to be unique!

I have no idea if I’m too paranoid here… nonetheless, it shouldn’t hurt either to add a simple assert_ne!(hi, 0) at the end of the function.

3 Likes

Thanks for pointing this out; I just pushed v0.1.5 with this fix.

I've been trying to figure out, why is it important for soundness that an IndirectGuestCell always returns the same GuestCell? By my understanding, borrowing a guest guest effectively borrows the value with key guest.id in every GuestCell in existence, including GuestCells that have been leaked or dropped. So if an IndirectGuestCell decides to pass you a different GuestCell all of a sudden, at worst you'll get an unexpected value, a panic, or a leak. Am I missing something, or is this a property that mvcc_cell is depending on for soundness?

(As a corollary, can't GuestCell<T> implement Send + Sync + UnwindSafe + RefUnwindSafe for all T? Its values can only be accessed or dropped with the proper Guest<'_>, which is !Send + !Sync + !UnwindSafe + !RefUnwindSafe due to the IndirectGuestCells it stores.)

1 Like

This might be right— I didn't do that part of my soundness analysis particularly rigorously, and defaulted to stating my requirements as an unsafe precondition instead of examining them too closely. It's also possible that things changed during development that made the unsafe unnecessary. There were two things that made me think twice about safety here:

  • get() and friends extend the lifetime of their returned reference beyond the lifetime of &self in IndirectGuestCell::borrow(), and instead relies on keeping an instance of the IndirectGuestCell. Moving a GuestCell around won't move the values it's holding, but dropping it will deallocate them, potentially leading to a dangling reference— The requirement to always return the same GuestCell implies a requirement to keep it alive.
  • For correctness, Guest needs to access the same cell on Drop to deallocate its private values. There's enough unsafe in this crate that I didn't want to untangle whether or not that was also a soundness issue.

Edit: I just realized that my thinking in point (1) was true when I stored Box<T>s, but when I switched to storing raw pointers, I didn't bother with a Drop implementation because it would be superfluous in normal operation: Each corresponding Guest will be dropped first and clean up its own storage space in the GuestCell.


Again, this is probably correct. When I set up the Send and Sync impls, I assumed that the Guest might be able to move between threads somehow (either now or in the future). They're also on the edge of my unsafe working knowledge: Not so scary that I avoid them, but also not familiar enough to feel confident in my analysis.


mvcc_cell isn't relying on it directly for soundness (I think), but it was introduced to support mvcc_cell: Every guest_cell there is owned by a struct that's stored inside an Arc already, and I wanted to avoid the double-Arc indirection.

It would be unsound for a GuestCell to deallocate its values. An evil IndirectGuestCell can soundly drop its GuestCell if it detects it's been moved or dropped, so dropping the GuestCell must not invalidate the value pointers.

I've been thinking about this crate a fair bit. Really, all the unsafe code can be stripped down to a simple primitive (@steffahn, does this primitive look sound to you?):

use std::{panic::UnwindSafe, ptr::NonNull, sync::Mutex};

fn get_unique_u64() -> u64 { ... }

#[derive(Debug)]
pub struct Key(u64);

#[derive(Debug)]
pub struct LockedBox<T: ?Sized>(u64, NonNull<T>);

unsafe impl<T: ?Sized + Send> Send for LockedBox<T> {}
unsafe impl<T: ?Sized + Sync> Sync for LockedBox<T> {}
impl<T: ?Sized + UnwindSafe> UnwindSafe for LockedBox<T> {}

impl Key {
    pub fn new() -> Self {
        Self(get_unique_u64())
    }

    pub fn lock<T: ?Sized>(&self, b: Box<T>) -> LockedBox<T> {
        let ptr = NonNull::new(Box::into_raw(b)).unwrap();
        LockedBox(self.0, ptr)
    }

    pub fn unlock<T: ?Sized>(&mut self, b: LockedBox<T>) -> Box<T> {
        assert!(self.0 == b.0);
        unsafe { Box::from_raw(b.1.as_ptr()) }
    }

    pub fn open<'a, T: ?Sized>(&'a self, b: &LockedBox<T>) -> &'a T {
        assert!(self.0 == b.0);
        unsafe { b.1.as_ref() }
    }

    pub fn open_mut<'a, T: ?Sized>(&'a mut self, b: &LockedBox<T>) -> &'a mut T {
        assert!(self.0 == b.0);
        unsafe { &mut *b.1.as_ptr() }
    }
}

(This pattern is trivially extensible to a LockedRc, LockedArc, etc.) Anyway, the idea is that the LockedBox (i.e., the GuestCell) doesn't have any ownership of the value it points to: it's basically just a pointer. Its only purpose is to remember the ID of its associated Key, and to act as a token for unlock(), to prevent the same box from being unlocked twice. The real ownership is handled entirely by the Lock (i.e., the Guest).

The main differences between the two APIs are that

  • Guest::set() requires a &mut Guest, since it "unlocks" the previous value before "locking" a new value;
  • the IDs are stored in the keys of the GuestCell, instead of right next to their associated pointers; and
  • a Guest keeps references to its GuestCells so that it can "unlock" all of its values on drop.

Perhaps you might find this reduction insightful; I'm somewhat surprised that a primitive like this doesn't already appear to exist.

2 Likes

This is why IndirectGuestCell is marked unsafe: The safety condition says that it must always be ready to return a reference to the same GuestCell, which precludes it being dropped while a copy of the IndirectGuestCell is stored in a Guest. That, combined with Guest keeping its IndirectGuestCells until drop, makes GuestCell dropping its contents on drop sound.

But GuestCell doesn't do that anymore, which makes the unsafe on IndirectGuestCell superfluous (as you've demonstrated here). It also makes the safety story much simpler, which is always a good idea.


LockedBox is a nice primitive, and I may rewrite GuestCell to use something like it internally. My initial attempts tried to use qcell for the access control, which also relies on unique integer ids, but I could never get it to quite work.

It probably makes sense to also provide a replace(&mut self, &LockedBox<T>, Box<T>)->Box<T> method so that it's possible to replace a ?Sized value without destroying the LockedBox.

What I'm trying to say is that the safety precondition as written, "borrow must always return the same GuestCell", is insufficient to preclude the GuestCell being dropped in the way you describe. To illustrate:

/*
[dependencies]
guest_cell = "=0.1.0"
*/

use guest_cell::{Guest, GuestCell, IndirectGuestCell};
use std::{
    borrow::Borrow,
    cell::Cell,
    panic::{self, AssertUnwindSafe},
    ptr,
    rc::Rc,
};

struct EvilBorrow<T>(Cell<*const EvilBorrow<T>>, Cell<Option<Rc<T>>>);

impl<T> Borrow<T> for EvilBorrow<T> {
    fn borrow(&self) -> &T {
        let ptr = self.0.get();
        if ptr.is_null() {
            self.0.set(self);
        } else if ptr != self {
            self.1.set(None);
        }
        // SAFETY: This reference can only be invalidated after `*self` is dropped or
        // moved, which necessarily ends the lifetime of the `self` reference. Therefore,
        // the lifetime of the returned reference is consistent with the signature of
        // this function.
        let option = unsafe { &*self.1.as_ptr() };
        option.as_ref().unwrap()
    }
}

// SAFETY: `EvilBorrow::borrow()` always returns a reference to the same
// `GuestCell<T>`, if it returns at all.
unsafe impl<T> IndirectGuestCell for EvilBorrow<GuestCell<T>> {
    type Inner = T;
}

fn main() {
    let cell = Rc::new(GuestCell::default());
    let mut guest = Guest::default();
    let wrapper = EvilBorrow(Cell::new(ptr::null()), Cell::new(Some(Rc::clone(&cell))));
    panic::catch_unwind(AssertUnwindSafe(|| {
        guest.set(wrapper, Box::new("Hello, world!"));
    }))
    .unwrap_err();
    println!("{}", guest.get(cell).unwrap());
}
1 Like

If I was feeling pedantic, I'd point out that panicing is not returning at all, and therefore EvilBorrow does not uphold the requirement that borrow "always returns the same GuestCell".

But that's a silly argument to get into as it fundamentally turns on the minutiæ of the soundness criteria I wrote, which could admittedly be more explicit. Especially given that standard Rust convention is that it's generally OK to panic instead of returning if an invariant can't be upheld.

In practice, though, I have a bad habit of forgetting to think about how to uphold soundness after something panics; thanks for the reminder that I need to consider this case.

Looking at this now. I’m noticing a variance problem. LockedBox is an interior mutability primitive, and must me invariant in T :slight_smile:

fn main() {
    let mut k = Key::new();
    let b = k.lock(Box::new(""));
    let r = k.open_mut(&b);
    let s = String::from("Hello World!");
    *r = &s;
    let s_ref: &'static str = *k.unlock(b);
    println!("{s_ref}");
    drop(s);
    println!("{s_ref}");
}
Hello World!
���\BV�k�
2 Likes

@LegionMammal978 similarly… the Send/Sync impls must also operate as the ones for interior mutability primitives. I.e., one needs a T: Send + Sync bound for LockedBox<T>: Sync!

2 Likes

Right, I see what you mean; the Send and Sync impls would have to be adjusted likewise. I wanted upcasting on the T to work as expected, but for that that to work I'd need T to be a parameter on the Key, which has standard ownership properties. (The Locked type in general is pretty weird to think about; all it does is assert the continued existence of its referent on the heap.) Now I'll have to figure out whether Locked<T>/Key vs. Locked/Key<T> would be the better option for the crate I'm working on which generalizes this concept.

1 Like

Due to how the lifetimes work, one even needs the full T: Send + Sync for LockedBox<T>: Send, too.

First &T reference can be created on one thread, the LockedBox<T> then sent, and the second &T reference created on another thread (both threads would have a &Key reference, and Key is Sync).

2 Likes

Locked / Key<T> can be mostly emulated by Key containing a HashMap<LockId,T> which doesn’t need this kind of trickery.

Locked<T>, on the other hand, lets a single Key unlock arbitrarily many different types without needing to declare them up front. I can’t think of any other way to do that.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.