Reinventing From Scratch — Rc<T>

Chapter 2 — Allocation Layout & Header Design

We represent an Rc<T> allocation as a single tail-allocated block with a header immediately followed by the value T. This layout is cache-friendly and ensures that cloning and upgrading only touch a small, well-localized structure.

2.1 The header

use std::cell::Cell;

#[repr(C)]
struct RcBox<T> {
    strong: Cell<usize>, // number of MyRc<T> owners
    weak:   Cell<usize>, // number of MyWeak<T> + implicit weak (1 when strong > 0)
    value:  T,           // inlined payload
}

#[repr(C)] gives us a predictable layout: counts first, then value.
Cell<usize> provides interior mutability: we can update counts through a shared reference to the header without &mut self.
value: T is tail-allocated: RcBox<T>’s size includes the value’s size; a single Layout::new::<RcBox<T>>() is sufficient for allocation and deallocation.

2.2 Allocation & deallocation helpers

We allocate and free the entire block with the same Layout. This is crucial: a mismatch is UB.

use std::alloc::{alloc, dealloc, Layout};

fn layout_of_rcbox<T>() -> Layout {
    Layout::new::<RcBox<T>>()
}

unsafe fn alloc_rcbox<T>(value: T) -> *mut RcBox<T> {
    let layout = layout_of_rcbox::<T>();
    let p = alloc(layout) as *mut RcBox<T>;
    if p.is_null() { panic!("allocation failed"); }
    // Write the header+value in one shot, moving `value` in.
    std::ptr::write(p, RcBox {
        strong: Cell::new(1),
        weak:   Cell::new(1), // implicit weak
        value,
    });
    p
}

unsafe fn dealloc_rcbox<T>(p: *mut RcBox<T>) {
    dealloc(p.cast(), layout_of_rcbox::<T>());
}

2.3 Why not allocate header and value separately?

We want a single pointer to the block to be the identity of our shared object. A split allocation would involve two frees and extra failure modes if one succeeds and the other fails, complicating recovery on panics.

2.4 Soundness corner

Never deallocate before dropping value (once).
Never decrement counts below zero (wrapping usize would be catastrophic).
Never double-drop: the code path that drops value must run exactly once per allocation.

2.5 Visualization

          +----------------------+
header →  | strong: Cell<usize>  |
          | weak:   Cell<usize>  |
          | value:  T            |  ◀─ single allocation
          +----------------------+

Cloning Rc bumps strong; dropping an Rc decrements it and may drop value. Dropping a Weak only touches weak and may free the block if both counts are zero.

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.

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)

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.

Layout and Header: RcBox<T>

Reinventing From Scratch — Rc<T>

Chapter 2 — Allocation Layout & Header Design

2.1 The header

2.2 Allocation & deallocation helpers

2.3 Why not allocate header and value separately?

2.4 Soundness corner

2.5 Visualization

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