Public Types and Invariants

Reinventing From Scratch — Rc<T>

Chapter 3 — Public Types & Invariants

We represent Rc and Weak as thin wrappers around a non-null pointer to RcBox<T>. We intentionally make them !Send and !Sync by not adding any auto traits and by relying on Cell inside the header.

use std::{marker::PhantomData, ptr::NonNull};

pub struct MyRc<T> {
    ptr: NonNull<RcBox<T>>,
    _marker: PhantomData<RcBox<T>>, // prevents auto traits
}

pub struct MyWeak<T> {
    ptr: NonNull<RcBox<T>>,
    _marker: PhantomData<RcBox<T>>,
}

3.1 Invariants to uphold

  1. ptr points to a valid RcBox<T> until the allocation is freed.
  2. strong equals the number of live MyRc<T> instances.
  3. weak equals the number of live MyWeak<T> instances plus 1 implicit weak when strong > 0.
  4. While strong > 0, the value: T is initialized and must be dropped exactly once when strong transitions to zero.
  5. The allocation is deallocated only when strong == 0 && weak == 0.

3.2 Constructor

impl<T> MyRc<T> {
    pub fn new(value: T) -> Self {
        unsafe {
            let p = alloc_rcbox(value);
            Self { ptr: NonNull::new_unchecked(p), _marker: PhantomData }
        }
    }
}

3.3 Why NonNull?

Using NonNull<RcBox<T>> states the invariant that our internal pointer is never null after successful construction. It avoids sentinel Option overheads and communicates intent.

3.4 API surface overview

  • Clone/Drop for MyRc<T>: bump and dec counts for strong.
  • downgrade → MyWeak<T>: bump weak.
  • upgrade on MyWeak<T>: read strong; if > 0, bump strong and return Some(MyRc<T>) else None.
  • Utilities: strong_count, weak_count, ptr_eq, get_mut, try_unwrap.

⚠️ All increments/decrements are via Cell: single-thread only. Moving MyRc<T> across threads is a correctness hole; don’t do it.

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.

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

  1. Create root, child1, child2 as MyRc<Node>.
  2. Call adopt(&root, &child1) and adopt(&root, &child2).
  3. 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: 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)

  1. 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.

  2. 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.

  3. Implement Rc::make_mut that clones T on write if strong > 1.
    Hint: This requires T: Clone and either temporary ownership or RefCell<T>.

  4. 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.

  5. Benchmark cloning vs upgrading using Criterion.
    Hint: Hot loop with b.iter(|| { let _ = a.clone(); }) vs let _ = w.upgrade(); from a pre-made Weak.

Suggested Further Reading

  • Rustonomicon: Reference Counting and Ownership Models
  • The std::rc source code (annotated with comments on drop order)
  • Swift’s ARC vs Rust’s RC: similarities and differences in move semantics
  • CPython’s refcounting: GIL-enabled safety vs Rust’s type-level guarantees

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

  1. Create root, child1, child2 as MyRc<Node>.
  2. Call adopt(&root, &child1) and adopt(&root, &child2).
  3. 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: 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)

  1. 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.

  2. 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.

  3. Implement Rc::make_mut that clones T on write if strong > 1.
    Hint: This requires T: Clone and either temporary ownership or RefCell<T>.

  4. 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.

  5. Benchmark cloning vs upgrading using Criterion.
    Hint: Hot loop with b.iter(|| { let _ = a.clone(); }) vs let _ = w.upgrade(); from a pre-made Weak.

Suggested Further Reading

  • Rustonomicon: Reference Counting and Ownership Models
  • The std::rc source code (annotated with comments on drop order)
  • Swift’s ARC vs Rust’s RC: similarities and differences in move semantics
  • CPython’s refcounting: GIL-enabled safety vs Rust’s type-level guarantees