Implementing a reference-counted pointer

struct Inner<T> { strong: Cell<usize>, value: T }
pub struct MyRc<T> { ptr: NonNull<Inner<T>>, _marker: PhantomData<Inner<T>> }

pub fn rc_script(ops: Vec<String>) -> Vec<i64>

Implement a reference-counted pointer from scratch, then run a script of operations over sixteen handle slots. The allocation is made with Box::leak, the count lives in a Cell<usize> next to the value, and the last handle to go away frees it — exactly once.

An out-of-range slot, or an operation on an empty slot, emits -1. Note that assigning into an occupied slot drops what was there — so clone 0 0 is a real edge case, not a typo.

The starter derives Clone. That is the trap.

The first invariant that is a number

Everything you have built so far had a range invariant: len <= cap, “these slots are initialised”, “this pointer is inside that allocation”. MyRc‘s is different and harder:

strong equals the number of live handles. Exactly. At all times.

Too high and the allocation leaks. Too low and it is freed while handles still point at it — a use-after-free. There is no slack, and no operation is allowed to leave it temporarily wrong in a way an observer could see.

::: question #[derive(Clone)] on MyRc<T> compiles. What does the generated code do, and why is it a guaranteed double free? It copies the pointer and the PhantomData field-by-field, and does not touch the count.

NonNull<T> is Copy, so the derived clone is a bitwise copy of the struct. You now have two MyRc handles and a strong of 1. The first one to be dropped sees count == 1, concludes it is the last, and frees the allocation. The second one then drops, reads a strong cell inside freed memory, and frees it again.

This is the best #[derive] trap in the language, because the derive is usually right. #[derive(Clone)] means “clone every field”, and for almost every struct that is exactly the semantics you want. It is wrong here for one reason: the struct’s meaning is not “these fields” but “one unit of a shared count”, and only a hand-written Clone can maintain the count.

The general rule worth taking away: any type whose invariant spans more than its own fields must not derive the traits that operate field-by-field. :::

Four bugs, three of them ordering

Decrement then check, instead of check then free. Writing

self.inner().strong.set(count - 1);
if self.inner().strong.get() == 0 { /* free */ }

reads the strong cell twice, and the second read happens on the last handle’s path after you have already committed to freeing. It works today and it is a trap: any future code between those two lines touches an allocation that is about to disappear. Check count == 1 first, then free without writing to the cell at all — the allocation is going away, there is nobody left to read it.

Freeing on count == 0 after decrementing. Same shape, worse: if you free and then decrement, you have written to freed memory.

Deref returning a &T with the wrong lifetime. fn deref(&self) -> &T ties the reference to &self, which is what you want. If you write a helper returning &'a T for an unconstrained 'a, the caller picks the lifetime and can outlive the handle — an unbounded lifetime, and a dangling reference from entirely safe code.

Refcount overflow. This one is the interesting one.

mem::forget(rc.clone()) in a loop

Both Clone and mem::forget are safe functions. So this is safe code:

loop { std::mem::forget(rc.clone()); }

Every iteration increments strong and never decrements it. On a 64-bit machine that takes essentially forever; on a 32-bit machine it is minutes. When the counter wraps past usize::MAX it comes back to zero, and now the next drop of a real handle sees count == 1, frees the allocation, and every other live handle is dangling.

A use-after-free reachable from entirely safe code is an unsoundness in your API, regardless of how absurd the program that triggers it is. std’s answer is to abort on overflow — not panic, abort, because a panic could be caught and the program continue with a corrupted count. Your implementation must do something equivalent; an assert! that the count is not already usize::MAX is acceptable here, and the write-up should say why std chose the stronger hammer.

::: question Why is “nobody would ever write that loop” not a defence? Because soundness is a property of the API, not of the current callers.

An API is unsound if some safe caller can cause undefined behaviour. It does not matter whether such a caller exists in your codebase today. Somebody will write a generic function that clones handles in a retry loop; somebody will deserialise attacker-controlled data into a structure that clones; somebody will port your crate to a 16-bit embedded target where usize::MAX is 65 535.

The discipline this teaches is worth more than the specific case: when you build a safe abstraction over unsafe code, the question is never “is this reachable” but “is this reachable in principle from safe code“. If yes, you must handle it — and “make the degenerate case abort” is a completely legitimate way to handle it. Turning a soundness hole into a loud, immediate process death is a real engineering tool, not a cop-out. :::

Send, Sync, and a nice accident

MyRc<T> must be neither Send nor Sync. The count is a plain Cell<usize> — non-atomic — so two threads incrementing it concurrently is a data race, which is undefined behaviour, which would let two handles believe they are the last.

You get that for free: MyRc holds a NonNull, raw pointers are !Send and !Sync, and auto traits propagate. Nothing to write, nothing to remember. It is worth pausing on, because it is the auto-trait system doing exactly the right thing by default — and it is the reason item 17.16 had to opt in with unsafe impl for MyVec, where the conservative answer was too conservative.

Arc differs from Rc in precisely one place: an AtomicUsize instead of a Cell<usize>, plus the memory orderings that make the decrement-and-free race safe. Everything else is the same code.

PhantomData<Inner<T>>

T already appears in ptr: NonNull<Inner<T>>, so the marker is not needed to satisfy E0392. It is there to say this type owns an Inner<T> — which is what the drop-checker and, more importantly, the next reader should believe of a handle that can free one. Item 17.19 unpacks what PhantomData does and does not do, including the fact that since RFC 1238 a type with a Drop impl is already assumed to own its generic parameters, so this particular marker is documentation rather than machinery.

What this grader cannot check

The count sequence is fully observable, so a #[derive(Clone)] or an off-by-one in the drop path fails a test rather than merely being wrong. What is not observable is a leak: if your Drop never frees, every case here passes. Nor can anything here detect the overflow path — you would have to run the loop. Write the guard because the argument requires it, not because a test demands it.

Remember the grade is compile + tests + clippy -D warnings.