Reinventing From Scratch — Rc<T>

Chapter 5 — `clone`, `drop`, and Count Getters

5.1 Cloning bumps `strong`

impl<T> Clone for MyRc<T> {
    fn clone(&self) -> Self {
        unsafe {
            let b = self.ptr.as_ref();
            let n = b.strong.get();
            b.strong.set(n.checked_add(1).expect("strong overflow"));
        }
        Self { ptr: self.ptr, _marker: std::marker::PhantomData }
    }
}

We use checked_add to make overflow impossible; in real code you might abort on overflow (std uses saturating counters—but overflow is practically unreachable).

5.2 Dropping a strong owner

impl<T> Drop for MyRc<T> {
    fn drop(&mut self) {
        unsafe {
            let b = self.ptr.as_ref();
            let n = b.strong.get();
            if n == 1 {
                // last strong: drop value & maybe free
                drop_strong_then_maybe_free(self.ptr.as_ptr());
                b.strong.set(0);
            } else {
                b.strong.set(n - 1);
            }
        }
    }
}

5.3 Observability

Public getters mirror std’s ergonomics:

impl<T> MyRc<T> {
    pub fn strong_count(this: &Self) -> usize { unsafe { this.ptr.as_ref().strong.get() } }
    pub fn weak_count(this: &Self) -> usize {
        unsafe {
            let b = this.ptr.as_ref();
            let s = b.strong.get();
            let w = b.weak.get();
            if s > 0 { w - 1 } else { w }
        }
    }
    pub fn ptr_eq(a: &Self, b: &Self) -> bool { a.ptr == b.ptr }
}

5.4 Micro-optimizations and cache behavior

Counts are in the same cache line as T on many targets; consider padding if false sharing with hot data occurs (rare in single-threaded apps).
Clones and upgrades touch only the header, so repeated operations are cache-friendly.

5.5 Gotchas

Forgetting to consume the implicit weak on last-strong drop → leaked allocation if no Weak exist.
Decrementing weak too many times → underflow and potential double-free on final Weak::drop.

Notes & Asides

Reference counting is deceptively simple: increments are easy; decrements must be exact.
Always document the invariants in prose before writing unsafe code.
Prefer small, focused unsafe blocks. Keep them near proofs.
Think in two layers: value lifetime (strong) vs allocation lifetime (weak).
Keep an eye on aliasing: shared references to interior-mutable fields are still mediated by Cell.

Notes & Asides

Reference counting is deceptively simple: increments are easy; decrements must be exact.
Always document the invariants in prose before writing unsafe code.
Prefer small, focused unsafe blocks. Keep them near proofs.
Think in two layers: value lifetime (strong) vs allocation lifetime (weak).
Keep an eye on aliasing: shared references to interior-mutable fields are still mediated by Cell.

Notes & Asides

Reference counting is deceptively simple: increments are easy; decrements must be exact.
Always document the invariants in prose before writing unsafe code.
Prefer small, focused unsafe blocks. Keep them near proofs.
Think in two layers: value lifetime (strong) vs allocation lifetime (weak).
Keep an eye on aliasing: shared references to interior-mutable fields are still mediated by Cell.

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

We maintain the following invariants for every allocation of RcBox<T>:

I1 (Header Validity): The fields strong and weak are valid usize counters that never underflow or overflow.
I2 (Value Liveness): value: T is initialized iff strong > 0. Equivalently, strong == 0 implies value has been dropped.
I3 (Allocation Liveness): The allocation is considered live iff strong + weak > 0.
I4 (Implicit Weak): While strong > 0, the weak counter includes an implicit unit that represents the allocation’s ownership by the strong regime. When strong becomes 0, we consume exactly one unit from weak.
I5 (Deallocation Condition): The allocation is deallocated iff strong == 0 && weak == 0.
I6 (Alias Soundness): get_mut only returns &mut T when strong == 1. No two &mut T aliases may exist simultaneously.
I7 (Upgrade Correctness): Weak::upgrade() returns Some iff it can soundly increment strong (i.e., strong > 0 at the time of the increment). Otherwise it returns None without touching memory after deallocation.

These invariants are checked conceptually at every mutating operation: clone, drop, downgrade, upgrade, get_mut, and try_unwrap.

B. Proof Sketches

B.1 Single Drop of value

Let S be the number of strong owners. Only when S transitions from 1 to 0 do we call drop_in_place(value).
After the transition, value is logically absent (I2). No future path calls drop_in_place(value) again because all other Drop paths observe S > 0 or S == 0 and skip value drop.
Therefore the destructor of T runs exactly once.

B.2 No Use-After-Free in upgrade

The allocation is freed only when S == 0 && W == 0 (I5).
upgrade first reads S. If S == 0, it returns None and does not dereference value nor mutate S.
If S > 0, it increments S before producing a MyRc<T>. Since writes to Cell are instantaneous w.r.t. this single-threaded model, either the increment happens first (then we are safe) or a concurrent decrement is impossible (no multi-threading). Hence no racing free occurs.

B.3 Safety of get_mut

get_mut requires unique strong ownership (S == 1) to produce &mut T. If a second Rc existed, S would be greater than 1 and the method would refuse, preserving aliasing guarantees (I6).

C. Panic Safety Considerations

Destructors should not panic. If they do, Rust aborts during unwinding-from-unwinding; our model does not attempt to recover from double-panics.
Construction is panic-safe because allocation and initialization happen in a single ptr::write of RcBox<T>; if panic occurs before storing, the program has not published the pointer.
Reduction operations (drop) use explicit branches and avoid underflow; we do not use saturating arithmetic to prevent masking logic errors.

D. Edge Cases

Degenerate types: For T = () or other ZSTs, headers still exist and counts still function; the value drop is a no-op, but the ordering invariants remain required.
Self-referential graphs: Rc<T> does not move T in memory; address stability is preserved, but cycles still leak. Use Weak for back-edges.
ptr_eq and multiple allocations: ptr_eq only answers whether two Rcs refer to the same allocation, not whether T values are equal by PartialEq.

E. Micro-bench Hints

Cloning is a single Cell increment; microbench with criterion across hot loops.
Avoid creating/dropping Weak in tight loops unless necessary; it touches weak each time.
Prefer get_mut or try_unwrap when ownership is unique; it skips reference-cell borrow machinery.

Worked Example: A Tiny Tree with Parent Weak Links

use std::cell::{RefCell};
#[derive(Debug)]
struct Node {
    name: String,
    parent: RefCell<MyWeak<Node>>,
    children: RefCell<Vec<MyRc<Node>>>,
}

fn make_node(name: &str) -> MyRc<Node> {
    MyRc::new(Node {
        name: name.into(),
        parent: RefCell::new(MyRc::downgrade(&MyRc::new(Node{name:String::new(), parent:RefCell::new(MyWeak{ptr: unsafe{std::mem::transmute(1usize)}, _marker: std::marker::PhantomData}}, children: RefCell::new(vec![])}))), // placeholder, replaced on adopt
        children: RefCell::new(vec![]),
    })
}

// Helper: adopt `child` into `parent` (strong), set child's parent (weak)
fn adopt(parent: &MyRc<Node>, child: &MyRc<Node>) {
    *child.parent.borrow_mut() = MyRc::downgrade(parent);
    parent.children.borrow_mut().push(child.clone());
}

The above uses a placeholder trick to satisfy the compiler in an example-only context; in production you would construct nodes in two phases or use Default and then set links.

Walkthrough

Create root, child1, child2 as MyRc<Node>.
Call adopt(&root, &child1) and adopt(&root, &child2).
Dropping root eventually drops both children once nothing else points at them strongly; their parent fields are Weak and do not retain the tree.

Debugging Playbook

Symptom: Allocation never freed.
Check: Did you forget to consume the implicit weak when last strong dropped? Are there outstanding Weak?
Symptom: Double free on last Weak.
Check: Did you decrement weak both on the last-strong path and again in Weak::drop without the implicit-weak protocol?
Symptom: Use-after-free in upgrade.
Check: Are you freeing the allocation while weak > 0? Did you deallocate before decrementing the very last weak?
Symptom: UB in get_mut.
Check: Ensure you only return &mut T when strong == 1 at the exact time of check. Avoid creating &mut across code that might clone another Rc.

Q: Why not store counts adjacent to each strong handle, like a decentralized RC?
A: It complicates synchronization even in single-threaded contexts and makes upgrade semantics unclear. Centralized counts in a header give one source of truth.

Q: Can I make Rc<T> Send if T: Send?
A: Not without atomics. The counters themselves would race; Arc<T> exists for this purpose.

Q: What about memory ordering on a single thread?
A: In single-threaded Rust, the memory model reduces to program order for Cell. We rely on the lack of concurrency, not on fences.

Q: Why does weak_count subtract 1 when strong > 0?
A: To hide the implicit weak from public observers and match std’s API expectations.

Q: Are overflow checks necessary?
A: Practically, you won’t reach usize::MAX strong references. We still use checked_add in educational code to make logic errors obvious.

Exercises (With Hints)

Design a make_cyclic_pair() that intentionally creates a leaking 2-node cycle.
Hint: Store strong references in each node’s next field; verify with drop logs that destructors never run.
Prove that try_unwrap is linear in the size of T.
Hint: It performs a single ptr::read of T and conditional deallocation; no per-field work beyond Drop of T is forced.
Implement Rc::make_mut that clones T on write if strong > 1.
Hint: This requires T: Clone and either temporary ownership or RefCell<T>.
Add debug assertions: ensure that on last-strong drop, strong == 1 and weak >= 1.
Hint: These can be debug_assert!s to avoid release-mode overhead.
Benchmark cloning vs upgrading using Criterion.
Hint: Hot loop with b.iter(|| { let _ = a.clone(); }) vs let _ = w.upgrade(); from a pre-made Weak.

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

We maintain the following invariants for every allocation of RcBox<T>:

I1 (Header Validity): The fields strong and weak are valid usize counters that never underflow or overflow.
I2 (Value Liveness): value: T is initialized iff strong > 0. Equivalently, strong == 0 implies value has been dropped.
I3 (Allocation Liveness): The allocation is considered live iff strong + weak > 0.
I4 (Implicit Weak): While strong > 0, the weak counter includes an implicit unit that represents the allocation’s ownership by the strong regime. When strong becomes 0, we consume exactly one unit from weak.
I5 (Deallocation Condition): The allocation is deallocated iff strong == 0 && weak == 0.
I6 (Alias Soundness): get_mut only returns &mut T when strong == 1. No two &mut T aliases may exist simultaneously.
I7 (Upgrade Correctness): Weak::upgrade() returns Some iff it can soundly increment strong (i.e., strong > 0 at the time of the increment). Otherwise it returns None without touching memory after deallocation.

These invariants are checked conceptually at every mutating operation: clone, drop, downgrade, upgrade, get_mut, and try_unwrap.

B. Proof Sketches

B.1 Single Drop of value

Let S be the number of strong owners. Only when S transitions from 1 to 0 do we call drop_in_place(value).
After the transition, value is logically absent (I2). No future path calls drop_in_place(value) again because all other Drop paths observe S > 0 or S == 0 and skip value drop.
Therefore the destructor of T runs exactly once.

B.2 No Use-After-Free in upgrade

The allocation is freed only when S == 0 && W == 0 (I5).
upgrade first reads S. If S == 0, it returns None and does not dereference value nor mutate S.
If S > 0, it increments S before producing a MyRc<T>. Since writes to Cell are instantaneous w.r.t. this single-threaded model, either the increment happens first (then we are safe) or a concurrent decrement is impossible (no multi-threading). Hence no racing free occurs.

B.3 Safety of get_mut

get_mut requires unique strong ownership (S == 1) to produce &mut T. If a second Rc existed, S would be greater than 1 and the method would refuse, preserving aliasing guarantees (I6).

C. Panic Safety Considerations

Destructors should not panic. If they do, Rust aborts during unwinding-from-unwinding; our model does not attempt to recover from double-panics.
Construction is panic-safe because allocation and initialization happen in a single ptr::write of RcBox<T>; if panic occurs before storing, the program has not published the pointer.
Reduction operations (drop) use explicit branches and avoid underflow; we do not use saturating arithmetic to prevent masking logic errors.

D. Edge Cases

Degenerate types: For T = () or other ZSTs, headers still exist and counts still function; the value drop is a no-op, but the ordering invariants remain required.
Self-referential graphs: Rc<T> does not move T in memory; address stability is preserved, but cycles still leak. Use Weak for back-edges.
ptr_eq and multiple allocations: ptr_eq only answers whether two Rcs refer to the same allocation, not whether T values are equal by PartialEq.

E. Micro-bench Hints

Cloning is a single Cell increment; microbench with criterion across hot loops.
Avoid creating/dropping Weak in tight loops unless necessary; it touches weak each time.
Prefer get_mut or try_unwrap when ownership is unique; it skips reference-cell borrow machinery.

Worked Example: A Tiny Tree with Parent Weak Links

use std::cell::{RefCell};
#[derive(Debug)]
struct Node {
    name: String,
    parent: RefCell<MyWeak<Node>>,
    children: RefCell<Vec<MyRc<Node>>>,
}

fn make_node(name: &str) -> MyRc<Node> {
    MyRc::new(Node {
        name: name.into(),
        parent: RefCell::new(MyRc::downgrade(&MyRc::new(Node{name:String::new(), parent:RefCell::new(MyWeak{ptr: unsafe{std::mem::transmute(1usize)}, _marker: std::marker::PhantomData}}, children: RefCell::new(vec![])}))), // placeholder, replaced on adopt
        children: RefCell::new(vec![]),
    })
}

// Helper: adopt `child` into `parent` (strong), set child's parent (weak)
fn adopt(parent: &MyRc<Node>, child: &MyRc<Node>) {
    *child.parent.borrow_mut() = MyRc::downgrade(parent);
    parent.children.borrow_mut().push(child.clone());
}

The above uses a placeholder trick to satisfy the compiler in an example-only context; in production you would construct nodes in two phases or use Default and then set links.

Walkthrough

Create root, child1, child2 as MyRc<Node>.
Call adopt(&root, &child1) and adopt(&root, &child2).
Dropping root eventually drops both children once nothing else points at them strongly; their parent fields are Weak and do not retain the tree.

Debugging Playbook

Symptom: Allocation never freed.
Check: Did you forget to consume the implicit weak when last strong dropped? Are there outstanding Weak?
Symptom: Double free on last Weak.
Check: Did you decrement weak both on the last-strong path and again in Weak::drop without the implicit-weak protocol?
Symptom: Use-after-free in upgrade.
Check: Are you freeing the allocation while weak > 0? Did you deallocate before decrementing the very last weak?
Symptom: UB in get_mut.
Check: Ensure you only return &mut T when strong == 1 at the exact time of check. Avoid creating &mut across code that might clone another Rc.

FAQ (Extended)

Q: Can I make Rc<T> Send if T: Send?
A: Not without atomics. The counters themselves would race; Arc<T> exists for this purpose.

Q: What about memory ordering on a single thread?
A: In single-threaded Rust, the memory model reduces to program order for Cell. We rely on the lack of concurrency, not on fences.

Q: Why does weak_count subtract 1 when strong > 0?
A: To hide the implicit weak from public observers and match std’s API expectations.

Q: Are overflow checks necessary?
A: Practically, you won’t reach usize::MAX strong references. We still use checked_add in educational code to make logic errors obvious.

Exercises (With Hints)

Design a make_cyclic_pair() that intentionally creates a leaking 2-node cycle.
Hint: Store strong references in each node’s next field; verify with drop logs that destructors never run.
Prove that try_unwrap is linear in the size of T.
Hint: It performs a single ptr::read of T and conditional deallocation; no per-field work beyond Drop of T is forced.
Implement Rc::make_mut that clones T on write if strong > 1.
Hint: This requires T: Clone and either temporary ownership or RefCell<T>.
Add debug assertions: ensure that on last-strong drop, strong == 1 and weak >= 1.
Hint: These can be debug_assert!s to avoid release-mode overhead.
Benchmark cloning vs upgrading using Criterion.
Hint: Hot loop with b.iter(|| { let _ = a.clone(); }) vs let _ = w.upgrade(); from a pre-made Weak.

Clone, Drop, and Getters

Reinventing From Scratch — Rc<T>

Chapter 5 — `clone`, `drop`, and Count Getters

5.1 Cloning bumps `strong`

5.2 Dropping a strong owner

5.3 Observability

5.4 Micro-optimizations and cache behavior

5.5 Gotchas

Notes & Asides

Notes & Asides

Notes & Asides

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

B. Proof Sketches

C. Panic Safety Considerations

D. Edge Cases

E. Micro-bench Hints

Worked Example: A Tiny Tree with Parent Weak Links

Debugging Playbook

FAQ (Extended)

Exercises (With Hints)

Suggested Further Reading

Deep Dive: Formal Invariants, Proof Sketches, and Edge Cases

A. Formal Invariants

B. Proof Sketches

C. Panic Safety Considerations

D. Edge Cases

E. Micro-bench Hints

Worked Example: A Tiny Tree with Parent Weak Links

Debugging Playbook

FAQ (Extended)

Exercises (With Hints)

Suggested Further Reading