Cactusref: cycle-aware reference counting

announcements
1

That's very cool! I didn't know there were algorithms that could do that, I assumed mark and sweep was the only viable option. Do you know how it works?

4 Likes
2

It seems like a very interesting project and I'll keep it on my radar. However, the documentation leaves me with the impression, that it is not quite ready yet for usage beyond experimentation.

Rc can detect and deallocate cycles of Rc s through the use of Adopt . Cycle detection is a zero-cost abstraction.

I doubt, that zero-cost abstraction is the correct term here. If a manually written doubly-linked list is really not better than using Rc, then it needs to be backed up with a proof, e.g. comparing the resulting assembly and checking for equality. For a scoped GC, it might be the best possible implementation, but that is trivially true without a competing alternative implementation. Calling it a low-cost abstraction seems more fitting and honest.

CactusRef depends on several unstable Rust features and can only be built on a nightly toolchain. CactusRef reimplements several compiler internals from alloc, which means it is only safe to build CactusRef with the same nightly compiler as the one pinned in its rust-toolchain file.

While requiring nightly by itself isn't necessarily that bad, pinning the project to a single nightly version is very restrictive. I hope this restriction can be lifted in the near future, moving to a range of working nightly versions.

CactusRef relies on proper use of Adopt::adopt and Adopt::unadopt to maintain bookkeeping about the object graph for breaking cycles. These functions are unsafe because improperly managing the bookkeeping can cause the Rc drop implementation to deallocate cycles while they are still externally reachable. Failure to uphold Adopt ’s safety invariants will result in undefined behavior and held Rc s that point to members of the now deallocated cycle may dangle.

Requiring unsafe is unfortunate. The immediate question popping up in my mind is, why does it require unsafe (could this be changed in the future, either through an optional API with additional runtime checks or a macro enforcing and emitting correct usage of unsafe?) and what kind of unsafe does it protect me from writing myself (if the user has to take of every safety invariant, its usage seems unattractive to me)?

3

Hi @Phlopsi thanks for the feedback.

I've made some changes to the documentation and README to clarify CactusRef's experimental status and cleaned up the copy around "zero-cost abstractions". A better way to say what I meant is that cycle detection is opt-in; in the absence of adoptions, there is no runtime cost.

I've published a new version that has these documentation changes: https://crates.io/crates/cactusref/0.1.1.

CactusRef reimplements box_free from alloc. It may be the case that CactusRef works on newer nightlies, but until the pinned compiler version is updated, I haven't verified that this function is implemented the same way.

The unsafe here is similar in shape to NonZeroUsize::new_unchecked. CactusRef relies on and exploits the ownership annotations implied by calls to adopt and unadopt. Failure to use these APIs correctly will result in unsoundness, just like Some(NonZeroUsize::new_unchecked(0)) will. The type of unsafe the adoption API encapsulates for you is a 400+ line Drop implementation.

Adopt::adopt has two safety invariants which I don't think are particularly onerous: Adopt in cactusref - Rust

Thanks again for your feedback and I'm glad you find CactusRef interesting.

1 Like
4

You're guaranteed to be able to free a Box<T> produced pointer using std::alloc::dealloc, and to allocate a pointer later used as a Box<T> with std::alloc::alloc, so long as the pointer is de/alloc'd with the correct layout for T.

2 Likes
5

Ooo! Thanks for letting me know this. I've merged a PR that re-implements the deallocation using alloc::alloc::dealloc and unpinned the nightly toolchain. CI will now run with the latest nightly.

Thanks!

https://github.com/artichoke/cactusref/pull/45

2 Likes
6

I've put together a WIP PR that experiments with a safe adoption API: [WIP] Experiment with a safe adoption API by lopopolo · Pull Request #47 · artichoke/cactusref · GitHub

1 Like
8

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.