New crate: qcell, a statically-checked alternative to RefCell

#21

Looking in more detail at your implementation that tests exhausting the range of IDs, it’s still unsafe. Okay it panics if one thread gets max, but another thread will allocate a wrapped ID. Trying to undo the increment will race with all the other threads. Okay you can allow a buffer range to protect against that, but it seems messy. Also I don’t like panicking if IDs run out.

Thinking more about it, using features to switch the implementation globally isn’t that nice either, as this could potentially be used by several crates, maybe way down the dependency chain. It’s hard for a crate owner to reason about it if they don’t know what implementation they’re getting.

Finally I’ve found a way to solve this. I keep the current u32 owner ID. The current QCellOwner::new() will be moved to fast_new() and marked unsafe. Just that one call is marked unsafe because unsafe use of that call (e.g. calling it 2^32 times) is the only way for things to go wrong. The replacement “slow but safe” new() call will use a mutex and a free list to allocate owner IDs. This suits the pattern of ID allocation that I expect to see in practice, i.e. relatively small sets of owner IDs used by each component, but maybe very many components created and destroyed. The fast and slow implementations allocate from different pools of owner IDs. I think this cannot be used maliciously now.

I’ll get this tested and published soonish.

0 Likes

#22

Sounds great :slight_smile:

Well spotted for the multi threaded unsafety, by the way, I always forget that a panic does not cross thread boundaries. How could we theoretically solve that?

  1. we could use a Mutex;

  2. or we could have a static POISONED: AtomicBool with carefully crafted atomic operations and orderings to prevent data races;

    • But this sounds like reimplementing Mutex's logic => back to 1.

That’s why I like what you have suggested.

Aside

Since the problem is not trivial, I am thinking that there should be a crate with a gen_unique_id() method in it (I’ve found one but it does silently ignore overflows)

0 Likes

#23

Inspired from ::std::sync::atomic::AtomicUsize::fetch_update() (not yet stable)

/// Panics on overflow, no matter the thread.
fn gen_unique_id () -> usize
{
    use ::std::sync::atomic::{self, AtomicUsize};
    const ORDERING: atomic::Ordering = atomic::Ordering::Relaxed;

    static UNIQUE_ID: AtomicUsize = AtomicUsize::new(0);

    let mut uid = UNIQUE_ID.load(ORDERING);
    while let Some(next_id) = uid.checked_add(1) {
        debug_assert_ne!(next_id, 0, "uid did not wrap");
        match UNIQUE_ID
                .compare_exchange_weak(uid, next_id, ORDERING, ORDERING)
        {
            Ok(_) => return uid,
            Err(new_id) => uid = new_id,
        }
    }
    panic!("Monotonic id overflow!")
}
0 Likes

#24

Yes, it looks like that could work. However I don’t need that kind of unique ID now, because if it is going to run out, then I’d need more than u32 of them on all platforms. So that means atomic u64 which isn’t supported everywhere (and is still unstable in any case).

Anyway, I’ve just published version 0.1.1 of the crate with the new choice of slow/safe and fast/unsafe implementations of QCellOwner::new(). Both implementations can run indefinitely without running out of IDs, so long as no more than 2^31 are required at any one time.

Thanks for the feedback on this. Okay it gave me a headache for a couple of days but I guess that’s what’s necessary to get these issues out.

1 Like

#25

I’ve added LCell now to do something similar to GhostCell, i.e. lifetime-based ownership, but more similar to the other cell types in this crate. It passes all the tests that the other two cell types pass, and I’ve added a few more tests besides.

It seems this pattern of having a choice of using integer-ID, marker-type or lifetime to connect instances of two types together is repeated for other things as well. There was a discussion on Reddit about using types (in this case closure types) to connect an index type with an array type. This brought up some old discussions from 2015 about the invariant lifetime technique, which I’ve linked to from the LCellOwner docs. This is what I used as a reference for the LCell implementation. Hopefully this will help other people find the discussions in the future.

0 Likes

#26

Since 1.34 brings AtomicU64 into stable, what about going back to an atomic implementation of the uid? :smiley:

1 Like

#27

I already have an atomic implementation of the ID in the unsafe/fast version (which as I say is not at all unsafe unless you really try to exploit it). Also I’d rather stay with a u32 ID value.

I guess for atomic u64, you’d have to panic if they ever got to the end of the u64 range, whereas the current implementations will run indefinitely. Also, it appears that atomic u64 still isn’t guaranteed on all platforms. So I think best stay with the current code.

0 Likes