Safety: Single-Threadedness and !Send/!Sync

Reinventing From Scratch — Rc<T>

Chapter 8 — Safety, Single-Threadedness, and Why Rc is !Send/!Sync

Rc<T> is intentionally single-threaded. Its counts live in Cell<usize>, which provides non-atomic interior mutability. If two threads concurrently increment or decrement via Cell, the behavior is a data race—undefined behavior in Rust’s memory model.

8.1 Auto traits and negative bounds

Our MyRc<T> does not implement Send or Sync. The compiler will not auto-derive them because of the Cell usage in RcBox<T> and because we don’t opt into these traits. This matches std::rc::Rc<T> behavior.

8.2 What would go wrong across threads?

  • Lost updates: two clones racing could overwrite each other, leaving strong with a stale value.
  • Double-free: two drops racing could each believe they are the last and both destroy the value or free the block.
  • Stale reads in upgrade: observing strong > 0 while another thread decremented to 0 and dropped the value.

8.3 The Arc<T> contrast

Arc<T> uses atomic counters (AtomicUsize) with carefully chosen memory orderings to preserve correctness across threads. The price is instruction-level overhead; the benefit is thread-safety.

8.4 Practical guidance

  • Use Rc<T> in single-threaded contexts like GUI threads, WASM front-ends, event loops.
  • Use Arc<T> when any possibility of cross-thread sharing exists.
  • Converts between them are not implicit; design your APIs to make the choice explicit at boundaries.

8.5 Testing tips

Miri does not model data races; rely on the type system and reviews. If you need race detection, use sanitizers in C interop layers or design out the need to share at all.

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