Is there such a cell? limited runtime-checked immut refs only

help
1

I'm looking for a cell type that provides a compile-time fixed (via a const generic param, perhaps) maximum number of runtime checked (no lifetime param) immutable reference wrappers, which can then be deref'ed as needed to get actual &refs. It should panic on an attempt to create more than the max number of immutable reference wrappers, or if there are any existing wrappers when an attempt is made to drop the cell's contents. The point to the runtime checking is that the immutable reference wrappers must not have lifetime annotations because they will be owned by a collection that has a longer lifetime (but which has elements removed as needed to prevent those panics) than any of those referenced values. No Sync/Send needed.

Preferably, it should be very lightweight. Something like this can be done with Rc. But I only need at most 2 of those runtime checked immutable reference wrappers, and they never need to share ownership or allow mutability.

2

How do you plan to ensure this without lifetimes?

3

The runtime check. If the target value is dropped while there are still existing references, that drop will panic. Proper usage would require manually removing the reference wrappers from their collections and dropping them prior to dropping the referenced value. There would be some kind of reference count (enough bits for the small limit) in the source cell that would be updated by creation and dropping of the reference wrappers.

4

In order to be sound, I think this would need to abort instead of panic. Otherwise, you could have a use-after-free if the unwind is caught and one of the tokens still exists.

I suspect that any solution to your problem will end up looking very much like the internals of Rc, and you're unlikely to see much improvement from writing a new primitive. The limit mechanism you describe is basically a reference count, and you'll need to ensure a stable address somehow which probably means heap allocation.

1 Like
5

That would be OK.

I was afraid of that. Thanks, anyway.

6

I think this should work. I only read you Sync comment later so you can replace these either all with Relaxed access or with a Cell<usize>.

use std::ptr::NonNull;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::process::abort;

pub struct RTBorrowGuard<'a, T> {
    borrowed: &'a T,
    counter: AtomicUsize,
}

impl<'a, T> RTBorrowGuard<'a, T> {
    pub fn new(borrowed: &'a T) -> Self {
        Self {
            borrowed,
            counter: AtomicUsize::new(0),
        }
    }

    pub fn temporary_pin(&mut self) -> RTBorrowPin<T> {
        assert_eq!(*self.counter.get_mut(), 0);
        RTBorrowPin {
            borrowed: self.borrowed,
            counter: &self.counter,
        }
    }
}

pub struct RTBorrowPin<'a, T> {
    borrowed: &'a T,
    counter: &'a AtomicUsize,
}

impl<'a, T> Drop for RTBorrowPin<'a, T> {
    fn drop(&mut self) {
        if self.counter.load(Ordering::Acquire) != 0 {
            abort()
        }
    }
}

impl<'a, T> RTBorrowPin<'a, T> {
    pub fn borrow(&self) -> RTBorrow<T> {
        self.counter.fetch_add(1, Ordering::Relaxed);
        RTBorrow {
            data: NonNull::new((self.borrowed as *const T).cast_mut()).unwrap(),
            counter: NonNull::new((self.counter as *const AtomicUsize).cast_mut()).unwrap(),
        }
    }
}

pub struct RTBorrow<T> {
    data: NonNull<T>,
    counter: NonNull<AtomicUsize>,
}

impl<T> core::ops::Deref for RTBorrow<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        unsafe {
            self.data.as_ref()
        }
    }
}

impl<T> Drop for RTBorrow<T> {
    fn drop(&mut self) {
        unsafe {
            self.counter.as_ref().fetch_sub(1, Ordering::Release);
        }
    }
}
7

This is unsound because it relies on RTBorrowPin's Drop implementation always running. However it could be leaked (e.g. by std::mem::forget), in which case RTBorrow would be left with dangling pointers.

3 Likes
8

I was thinking about making a library similar to this, though without the limit on the number of borrows. Essentially variants of Rc and Arc that store their contents inline using pinning and abort the program if they go out of scope before all the borrows are gone. As @2e71828 said, just panicking is not sound as far as I know.

Why do you want to limit the number of guards? Do you think this makes sense to integrate into the pointer types? Since &T is Copy I don't really see the use case.

9

I've been thinking about this and I can see a couple of ways to fix the issue:

  • heap allocate both the T and the counter AtomicUsize. This avoids RTBorrow pointing to invalid memory after RTBorrowPin is leaked, because if that was the case the allocation would also be leaked and remain valid. The downside is that this effectively becomes an Arc/Rc without counter for Weak pointers and aborts on misuse instead of sharing ownership.

  • move ownership of the T in RTBorrowPin and require a Pin<&RTBorrowPin> in RTBorrowPin::borrow. This is sound because the Pin guarantees that the RTBorrowPin's memory won't be invalidated without calling its drop glue, meaning the pointer to the T and AtomicUsize will remain valid until the RTBorrowPin has a chance to abort. This has the advantage of not requiring a heap allocation, but users will have to deal with Pin (which really amounts to either doing pin!(rt_borrow_pin) or calling Box::pin which effectively falls back to the previous point.

  • use a callback-based API to ensure that RTBorrowPin's drop glue is executed when the callback returns. This has the advantage of being able to accept a borrowed &T, but the downside is that you cannot move the RTBorrowPin to the caller's scope. Moreover this API must be sync-only, since it relies on locals always being dropped before the stack memory is invalidated (this is the case for sync functions, but not async, and is also the reason that scoped async tasks are not possible; indeed this problem shares a lot of similarities with them).

1 Like
10

Isn't this just an Arc where you check strong_count() after cloning and fail if it's too big?

11

Two reasons. One is that I'd like the refcount to be small, potentially using existing unused bits. The other is that I know based on my app's design what the upper limit is, such that attempts to create more are obviously bugs that I'd like to know about asap. Of course, providing a way to access the refcount would allow the user to write their own assert - so maybe this reason isn't very useful.

However, if the refcount has to be part of a distinct heap allocation in order to enable pinning, then there's probably not much to be gained by making it very small. And, along those lines, there might not be much performance/resource gain vs. just basing this entirely on Rc. Maybe this is just my own stubborn reluctance, but it seems that Rc is overkill for cases where the ownership is not shared. Especially when only limited immutable borrows are needed.

12

I don't think you can pack the counter into unused bits of the contained value and still have it be generic. You could if you required users to implement an unsafe trait to store the recount within the value, but pushing the responsibility of unsafe onto users to safe a few bytes is probably not worth it in most cases.

The least space use you could reasonably get is using an u8 as a counter. But if the contained type has a higher alignment, you will again be rounded up to that, so probably even here you are not saving much.

The point of pinning was to avoid a heap allocation. You can pin values on the stack just fine using std::pin::pin. Pinning guarantees that drop runs before the memory is reused, so you can use it for all kinds of fun pointer things. The ref-count would live in that stack space along with the shared value. But yes, saving the heap allocation probably doesn't make much of a difference. For my use case, these are very long-lived anyway, which is why I haven't gotten around to making the library yet.

13

Stacked wouldn't work in my case. I need to own the values (or cells wrapping them) in a Vec<Option<...>>.