Project 2: Implement a Reference-Counted Smart Pointer (Rc)

Build a safe MyRc<T> with strong/weak counts, interior mutability for refcounts, and deterministic drop behavior.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1 week
Main Programming Language Rust (Alternatives: C++ for comparison)
Alternative Programming Languages C++ (shared_ptr), C (manual refcount)
Coolness Level High
Business Potential Medium
Prerequisites Ownership, lifetimes, raw pointers, Drop, basic unsafe
Key Topics Reference counting, weak refs, interior mutability, aliasing

1. Learning Objectives

By completing this project, you will:

  1. Implement a safe Rc-like smart pointer with correct refcount semantics.
  2. Use interior mutability (Cell/UnsafeCell) to mutate refcounts through shared references.
  3. Implement Weak to avoid memory leaks caused by cycles.
  4. Document and enforce safety invariants around allocation and deallocation.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Shared Ownership and Reference Counting

Fundamentals

Shared ownership means multiple owners can access the same heap allocation. In Rust, this is achieved with reference counting: each clone increments a counter, and each drop decrements it. When the count reaches zero, the allocation is freed. This model prevents double-free and use-after-free without a garbage collector. The cost is runtime overhead and the possibility of cycles that never drop. Rc<T> is single-threaded; Arc<T> is thread-safe and uses atomic refcounts. Understanding reference counting means understanding ownership transfer, Drop, and how to safely free exactly once.

Deep Dive into the concept

Reference counting is a runtime ownership model layered on top of Rust’s compile-time rules. The compiler allows multiple Rc<T> clones because the Rc itself owns a pointer to the heap allocation, not the allocation directly. The allocation lives in a separate control block that stores both the value and its counters. When you clone an Rc, you increment the strong count; when you drop, you decrement it. When the strong count hits zero, you drop the value. When both strong and weak counts hit zero, you free the control block. This two-level approach allows Weak pointers to observe the allocation without keeping it alive.

The real difficulty is keeping the counters consistent. Because Rc is not thread-safe, you can use Cell<usize> or UnsafeCell<usize> to mutate counts even when you only have &Rc<T>. This is interior mutability. The invariant is: all Rc instances for a given allocation must point to the same control block, and the counts must reflect the exact number of live Rc and Weak handles. Any bug here becomes a double-free, leak, or use-after-free. Rust’s type system cannot check this; you must prove it in your implementation.

Reference counting has deterministic drops, unlike tracing garbage collection. That makes it predictable but also means cycles leak. If A holds an Rc<B> and B holds an Rc<A>, the strong count never reaches zero. Weak is the escape hatch: you break the cycle by making one edge weak. When a strong count reaches zero, the value is dropped, but the control block remains until all weak references are gone. This ensures Weak::upgrade can safely check whether the allocation still exists.

Another subtlety is aliasing. Because multiple Rc<T> exist, you can have multiple shared references to the same value. This is safe only if mutation goes through a RefCell or another interior mutability primitive that enforces borrowing rules at runtime. Your MyRc<T> should implement Deref<Target = T> to allow shared access. You should not provide mutable access unless you also implement RefCell-like dynamic checks. This is the core of the aliasing contract: many readers, no unsynchronized writers.

There is also an API design decision: should your MyRc<T> be Clone or Copy? It must be Clone but never Copy, because copying without incrementing the count would break the invariant. This is an important lesson in designing safe abstractions: you explicitly choose which traits are allowed based on invariants. Similarly, you must decide whether MyRc<T> should be Send or Sync. The answer is no, unless you use atomics. Rust’s auto traits will help if you design the struct correctly.

Finally, Rc exposes the concept of “allocation + metadata” as a single unit. The control block layout must be stable and correctly aligned. A typical pattern is:

struct RcBox<T> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

You allocate this RcBox<T> on the heap and store a NonNull<RcBox<T>> inside the Rc. The Rc then dereferences to &T. The Weak stores the same pointer but does not affect the strong count. This design is simple, but it carries a crucial invariant: the pointer must remain valid until both counts reach zero.

How this fit on projects

This concept governs §3.2 (functional requirements), §4.2 (key components), and §5.10 (implementation phases). It is foundational for Project 9 (connection pool with shared ownership) and Project 8 (atomic refcounts for lock-free structures).

Definitions & key terms

  • Reference counting: Runtime ownership model using counters.
  • Strong count: Number of owning references.
  • Weak count: Number of non-owning references.
  • Control block: Heap allocation storing counters and the value.
  • Cycle: Two or more allocations that keep each other alive.

Mental model diagram (ASCII)

Rc ----+        +---------------------+
       |------> | strong | weak | val |
Weak --+        +---------------------+

How it works (step-by-step)

  1. Allocate RcBox<T> with strong=1, weak=0.
  2. Clone increments strong.
  3. Drop decrements strong; if strong==0, drop value.
  4. Weak pointers keep control block alive until weak==0.
  5. When strong==0 and weak==0, free the allocation.

Minimal concrete example

let a = MyRc::new(5);
let b = a.clone();
assert_eq!(*a, 5);
assert_eq!(*b, 5);
// drop a and b -> value dropped once

Common misconceptions

  • “Rc prevents all memory leaks.” Cycles still leak without Weak.
  • “Rc is thread-safe.” It is not; only Arc uses atomics.
  • “Rc gives mutable access.” It only gives shared access unless wrapped in RefCell.

Check-your-understanding questions

  1. Why do you need a weak count separate from the strong count?
  2. What happens if Rc is mistakenly Copy?
  3. Why must Rc<T> not implement Send by default?

Check-your-understanding answers

  1. Weak references must keep the control block alive even after the value is dropped.
  2. Copies would skip refcount increments, causing double-free.
  3. Refcount updates are not atomic, causing data races in threads.

Real-world applications

  • UI widget trees with shared nodes.
  • Compiler IR graphs with shared subtrees.
  • Caches with shared entries.

Where you’ll apply it

References

  • TRPL Ch. 15 (Smart pointers).
  • Rustonomicon: “Rc” and “Arc” chapters.
  • “Rust Atomics and Locks” on refcount design.

Key insights

Reference counting is ownership at runtime: the compiler trusts your counters.

Summary

Rc is safe because every clone and drop updates a shared counter that precisely tracks ownership.

Homework/Exercises to practice the concept

  1. Sketch the drop sequence for a cycle and explain why it leaks.
  2. Compare Rc vs Arc and list what changes for thread safety.
  3. Implement a tiny refcount in C to see the pitfalls.

Solutions to the homework/exercises

  1. Both nodes keep each other alive, so strong count never reaches zero.
  2. Arc uses atomic increments/decrements and has higher overhead.
  3. Manual refcount requires disciplined increments and decrements to avoid bugs.

2.2 Interior Mutability and Aliasing Rules

Fundamentals

Rust’s aliasing rule is simple: either one mutable reference or many shared references. Rc<T> gives you multiple owners, which means multiple shared references. To mutate the refcount, you need interior mutability: a way to mutate data through a shared reference. Cell and UnsafeCell are the fundamental tools. They allow mutation while maintaining Rust’s safety because the mutation is limited to small, copyable values (for Cell) or explicitly marked unsafe (for UnsafeCell). This is how Rc updates counts without requiring &mut self.

Deep Dive into the concept

Interior mutability is the mechanism that bridges Rust’s static borrow rules with practical shared ownership. Normally, if you have &T, you cannot mutate T. But Rc must mutate its refcounts even when only shared references exist. The language provides UnsafeCell<T> as a special marker that tells the compiler: “this memory may be mutated even through shared references.” Cell<T> is a safe wrapper around UnsafeCell for Copy types. By placing refcounts inside Cell<usize>, you can increment and decrement them with get and set without violating Rust’s aliasing model.

The key insight is that interior mutability is not a loophole; it is a controlled escape hatch. UnsafeCell removes the compiler’s assumption of immutability, but you are still responsible for maintaining higher-level invariants. In Rc, the invariant is that refcount updates are single-threaded. That means you can use non-atomic increments safely because no two threads can mutate the same Rc simultaneously. Rust enforces this by ensuring Rc<T> is not Send or Sync if it contains Cell. If you accidentally make Rc Send, you break the invariant and allow data races. This is why the internal type choices in Rc are so important: they influence auto trait derivation.

Aliasing also matters for the value itself. Rc<T> allows multiple aliases to the same value. This is safe because you only get &T, not &mut T. If you want mutation, you must wrap T in a RefCell<T>, which enforces borrow rules at runtime (panic on double mutable borrow). This is a trade-off: you lose compile-time guarantees in exchange for flexibility. It is the same story as refcounting: runtime checks replace static ones. Learning when to use RefCell is essential for building safe APIs.

In your implementation, interior mutability shows up in RcBox<T> refcounts. You must design your API so that the only mutation possible through &Rc<T> is the refcount update. That means no other shared state should be mutable. This keeps the unsafe boundary small and understandable. If you later extend the project with RefCell, you must clearly document the runtime borrow rules and show how they can panic on misuse.

Interior mutability also affects optimization. Because the compiler cannot assume immutability, it must reload values around UnsafeCell. This can make code slightly slower. For refcounting this is acceptable, but in high-performance contexts it can matter. The design lesson is that safety and performance trade-offs are explicit in Rust; you choose when to pay runtime costs.

How this fit on projects

You will apply this in §4.2 (component design), §5.10 (refcount updates), and §7.1 (pitfalls). It also appears in Project 3 (graph with Rc<RefCell<T>>) and Project 4 (mutex-based interior mutability across threads).

Definitions & key terms

  • Interior mutability: Mutating through shared references.
  • UnsafeCell: Core primitive for interior mutability.
  • Cell: Safe wrapper for Copy types.
  • RefCell: Runtime borrow-checked mutability.
  • Aliasing: Multiple references to the same memory.

Mental model diagram (ASCII)

&Rc<T>
  |
  +--> Cell<usize> (refcount)  <-- mutable even through &
  +--> T (value)              <-- immutable via &

How it works (step-by-step)

  1. Rc::clone reads the refcount from a Cell.
  2. It increments and writes back the count.
  3. No mutable reference is needed; the Cell handles it safely.
  4. The value T is still accessed immutably through Deref.

Minimal concrete example

let c = Cell::new(1);
c.set(c.get() + 1);

Common misconceptions

  • “Interior mutability is unsafe.” It is safe when used correctly.
  • “RefCell is the same as Mutex.” RefCell is single-threaded.
  • “Alias rules don’t matter with Rc.” They still matter for T.

Check-your-understanding questions

  1. Why does Rc use Cell<usize> instead of usize?
  2. When would you choose RefCell<T> over Cell<T>?
  3. Why does UnsafeCell affect compiler optimizations?

Check-your-understanding answers

  1. Because refcounts must be updated through shared references.
  2. When you need mutation of non-Copy data with runtime checks.
  3. The compiler can no longer assume the value is immutable.

Real-world applications

  • GUI trees where multiple widgets share state.
  • Caches with shared ownership in single-threaded contexts.

Where you’ll apply it

References

  • TRPL Ch. 15 (RefCell and interior mutability).
  • Rustonomicon: “UnsafeCell”.

Key insights

Interior mutability is how Rust safely updates shared metadata without violating aliasing rules.

Summary

Cell and UnsafeCell are the key building blocks that make refcounted ownership possible in Rust.

Homework/Exercises to practice the concept

  1. Implement a Cell-based counter and test aliasing behavior.
  2. Write a small example that panics with RefCell double mutable borrow.

Solutions to the homework/exercises

  1. Use Cell<usize> and clone a wrapper struct to show shared updates.
  2. Borrow mutably twice without dropping the first borrow.

2.3 Weak References, Cycles, and Drop Semantics

Fundamentals

Weak references are non-owning pointers to a shared allocation. They do not keep the value alive but can be upgraded to a strong reference if the value still exists. This allows you to break cycles in reference-counted graphs. Drop semantics in Rc are two-phase: when strong count hits zero, the value is dropped; when weak count also reaches zero, the allocation itself is freed. This separation ensures that Weak::upgrade can safely detect whether the value has been dropped.

Deep Dive into the concept

Reference cycles are the Achilles’ heel of refcounting. Consider two nodes, each holding an Rc to the other. Even if there are no external references, both strong counts remain at least 1, so the value is never dropped. This is a leak, not a crash, but it violates resource cleanup guarantees. The solution is a weak reference: a handle that points to the same control block but does not increment the strong count. In Rust’s Rc, Weak increments a separate weak count, ensuring the control block stays alive so you can detect that the value is gone. A Weak reference can be upgraded by checking if strong count > 0. If yes, you create a new Rc and increment strong; if no, upgrade returns None.

The two-phase drop process is fundamental. When the strong count goes to zero, you drop the value. This ensures Drop runs exactly once and releases resources. But you cannot free the allocation because weak references might still exist. If you freed the allocation immediately, upgrading a Weak could dereference freed memory. That’s why the control block persists until the weak count hits zero. This pattern is a common technique in systems programming and is also used in Arc.

Your implementation must clearly define the order of operations. In Drop for MyRc<T>, you decrement strong. If it becomes zero, you drop the value in place. Then you decrement the weak count for the implicit weak reference held by the strong references. If weak becomes zero, you deallocate. The details matter: if you forget the implicit weak, you might free the allocation too early. If you drop in the wrong order, you might access freed memory during value drop.

Weak references also influence API design. You must decide whether to expose downgrade and upgrade APIs similar to std Rc. You should also decide whether your Weak type implements Clone. It should, and cloning should increment the weak count. Like Rc, Weak must not be Copy.

Finally, cycles are not always bad. Sometimes you want them to keep data alive as long as there is any path in the graph. But refcounting alone cannot collect cycles; you need explicit design choices. This is a good moment to teach design: for parent-child relationships, usually the parent owns the children (strong), and children hold weak references to parents. That breaks cycles and allows deterministic cleanup.

How this fit on projects

This concept is applied directly in §3.2 (requirements for Weak), §5.10 Phase 2, and §7.1 (pitfalls). It’s also used in Project 3 (graph cycles) and Project 9 (pool handles that should not keep resources alive forever).

Definitions & key terms

  • Weak reference: Non-owning pointer to a shared allocation.
  • Upgrade: Convert Weak to Rc if value still exists.
  • Cycle leak: A refcount cycle that prevents cleanup.
  • Control block lifetime: The time until both strong and weak are zero.

Mental model diagram (ASCII)

strong=0 -> drop value
weak>0  -> keep control block
weak=0  -> free control block

How it works (step-by-step)

  1. Weak::clone increments weak count.
  2. Weak::upgrade checks strong count.
  3. If strong > 0, create new Rc and increment strong.
  4. When strong reaches zero, drop value.
  5. When weak reaches zero, free allocation.

Minimal concrete example

let a = MyRc::new(Node::new());
let w = MyRc::downgrade(&a);
drop(a);
assert!(w.upgrade().is_none());

Common misconceptions

  • “Weak prevents all leaks.” It prevents cycles only if you actually use it.
  • “Weak keeps the value alive.” It does not.
  • “Dropping value frees memory immediately.” Control block persists while weak exists.

Check-your-understanding questions

  1. Why does a strong Rc conceptually own an implicit weak ref?
  2. What happens if you free the control block when strong hits zero but weak > 0?
  3. How do you design a parent-child relationship with Weak?

Check-your-understanding answers

  1. So that the control block is kept alive until all Rc and Weak handles are gone.
  2. Weak::upgrade could dereference freed memory, causing UB.
  3. Parent holds strong to child; child holds weak to parent.

Real-world applications

  • Tree structures with parent pointers.
  • Observers that should not keep subjects alive.

Where you’ll apply it

References

  • TRPL Ch. 15 (Rc and Weak).
  • Rustonomicon: “Rc”.

Key insights

Weak references separate “observe” from “own.”

Summary

Weak is the escape hatch that makes refcounting practical for cyclic graphs.

Homework/Exercises to practice the concept

  1. Build a two-node cycle with strong refs and observe leak.
  2. Replace one edge with Weak and confirm cleanup.

Solutions to the homework/exercises

  1. Strong counts never reach zero.
  2. With Weak, strong counts drop to zero and value is freed.

3. Project Specification

3.1 What You Will Build

A Rust crate my_rc implementing a MyRc<T> and MyWeak<T> with Clone, Deref, downgrade, and upgrade APIs. The project includes a CLI demo and tests to validate refcount semantics.

3.2 Functional Requirements

  1. MyRc::new: allocate value with strong=1, weak=0.
  2. Clone: increment strong count and return new MyRc.
  3. Drop: decrement strong; drop value if strong==0.
  4. Weak: support downgrade and upgrade.
  5. Cycle demo: show leak with strong cycle and fix with weak.

3.3 Non-Functional Requirements

  • Safety: unsafe blocks are minimal and documented.
  • Correctness: refcounts remain consistent under clone/drop.
  • Usability: API mirrors std Rc for familiarity.

3.4 Example Usage / Output

$ cargo run --example rc_demo
strong=1 weak=0
strong=2 weak=0
strong=1 weak=0
value dropped at strong=0
exit code: 0

3.5 Data Formats / Schemas / Protocols

  • RcBox<T> layout: { strong: Cell<usize>, weak: Cell<usize>, value: T }.
  • MyRc<T>: NonNull<RcBox<T>> pointer.
  • MyWeak<T>: NonNull<RcBox<T>> pointer.

3.6 Edge Cases

  • Dropping last strong while weak still exists.
  • Upgrading weak after value dropped.
  • Overflow in refcount (detect and panic or error).

3.7 Real World Outcome

You will run demos that show both correct drops and cycle leaks.

3.7.1 How to Run (Copy/Paste)

cargo run --example rc_demo
cargo run --example cycle_demo

3.7.2 Golden Path Demo (Deterministic)

  • Create two clones and drop them in order.
  • Expect exactly one drop of value.

3.7.3 CLI Transcript (Success)

$ cargo run --example rc_demo
strong=1 weak=0
strong=2 weak=0
strong=1 weak=0
value dropped at strong=0
exit code: 0

3.7.4 Failure Demo (Cycle Leak)

$ cargo run --example cycle_demo
cycle created
strong=2 weak=0
warning: value not dropped (cycle)
exit code: 1

4. Solution Architecture

4.1 High-Level Design

MyRc<T> ---> RcBox<T> (heap)
MyWeak<T> -/

4.2 Key Components

Component Responsibility Key Decisions
RcBox<T> Stores counts + value Cell<usize> for counts
MyRc<T> Strong handle Clone, Deref
MyWeak<T> Weak handle upgrade checks strong
Examples Demos and tests Deterministic outputs

4.4 Data Structures (No Full Code)

struct RcBox<T> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

4.4 Algorithm Overview

Key Algorithm: Drop Logic

  1. Decrement strong.
  2. If strong==0, drop value.
  3. Decrement weak (implicit).
  4. If weak==0, deallocate.

Complexity Analysis:

  • Time: O(1) per clone/drop
  • Space: O(1) overhead per allocation

5. Implementation Guide

5.1 Development Environment Setup

cargo new my_rc
cd my_rc
cargo add thiserror

5.2 Project Structure

my_rc/
├── src/
│   ├── lib.rs
│   ├── rc.rs
│   └── weak.rs
├── examples/
│   ├── rc_demo.rs
│   └── cycle_demo.rs
└── tests/
    └── rc_tests.rs

5.3 The Core Question You’re Answering

“How can multiple owners safely share a single allocation, and still free it exactly once?”

5.4 Concepts You Must Understand First

  1. Reference counting and strong/weak semantics.
  2. Interior mutability using Cell.
  3. Drop order and control block lifetime.

5.5 Questions to Guide Your Design

  1. How will you store the control block and keep it aligned?
  2. When exactly should the value be dropped vs the allocation freed?
  3. How will you handle refcount overflow?

5.6 Thinking Exercise

Draw the control block layout and simulate refcount changes for clone/drop.

5.7 The Interview Questions They’ll Ask

  1. “Why does Rc leak cycles?”
  2. “Why is Rc not thread-safe?”
  3. “What is the difference between Rc and Arc?”

5.8 Hints in Layers

Hint 1: Use NonNull<RcBox<T>> and allocate with Box::new. Hint 2: Implement Clone to increment strong. Hint 3: Implement Drop to decrement and free when zero. Hint 4: Add a Weak type and use upgrade.

5.9 Books That Will Help

| Topic | Book | Chapter | |—|—|—| | Smart pointers | TRPL | Ch. 15 | | Unsafe invariants | Rustonomicon | “Rc” | | Concurrency contrast | Rust Atomics and Locks | Ch. 6 |

5.10 Implementation Phases

Phase 1: Control Block (2 days)

Goals:

  • Define RcBox<T> and allocate it on the heap.
  • Implement MyRc::new.

Checkpoint: A single MyRc drops the value once.

Phase 2: Clone/Drop (2-3 days)

Goals:

  • Implement strong refcount increments/decrements.
  • Add Deref for access.

Checkpoint: Clone and drop tests pass.

Phase 3: Weak + Cycles (2 days)

Goals:

  • Implement MyWeak and upgrade.
  • Demonstrate cycle leak and fix with weak.

Checkpoint: Cycle demo shows expected leak and fix.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |—|—|—|—| | Refcount storage | Cell vs AtomicUsize | Cell | Single-threaded design | | Drop order | value first vs allocation | Drop value, then free | Avoid use-after-free | | Overflow handling | panic vs error | Panic | Simplify contract |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |—|—|—| | Unit Tests | Refcount arithmetic | clone/drop sequences | | Integration Tests | CLI demos | rc_demo, cycle_demo | | Edge Case Tests | Weak upgrade after drop | upgrade returns None |

6.2 Critical Test Cases

  1. Clone twice, drop in varying order; value dropped once.
  2. Weak upgrade after last strong drop returns None.
  3. Cycle leak demo produces warning.

6.3 Test Data

seed=42
iterations=1000

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |—|—|—| | Forgetting implicit weak | Double free or use-after-free | Track implicit weak | | Making Rc Copy | Double free | Do not implement Copy | | Using Rc across threads | Data race | Use Arc instead |

7.2 Debugging Strategies

  • Log refcounts on clone/drop.
  • Use cargo miri test to catch UB.

7.3 Performance Traps

  • Excessive cloning in tight loops.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add strong_count and weak_count accessors.

8.2 Intermediate Extensions

  • Implement Arc with atomics.

8.3 Advanced Extensions

  • Add cycle detector for debug builds.

9. Real-World Connections

9.1 Industry Applications

  • UI trees and shared UI state.
  • Graph structures in compilers.
  • std::rc::Rc
  • std::sync::Arc

9.3 Interview Relevance

  • Explain reference counting trade-offs.
  • Describe cycle leaks and mitigation.

10. Resources

10.1 Essential Reading

  • TRPL Ch. 15.
  • Rustonomicon “Rc”.

10.2 Video Resources

  • RustConf talks on smart pointers.

10.3 Tools & Documentation

  • cargo miri

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain strong vs weak counts.
  • I can describe why cycles leak.
  • I can explain interior mutability.

11.2 Implementation

  • All refcount tests pass.
  • Drop runs exactly once.
  • Weak upgrade works correctly.

11.3 Growth

  • I can compare Rc and Arc in interviews.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • MyRc<T> supports clone/drop and correct refcounts.
  • CLI demo shows deterministic output and cycle failure.

Full Completion:

  • Includes Weak and upgrade semantics.

Excellence (Going Above & Beyond):

  • Thread-safe Arc extension and benchmarks.