Learn Rust Series (#35) - Weak References & Breaking Reference Cycles

scipio(71)

Published in

StemSocial

Words

2865

Reading

13 min

Listen

Play

21d

Learn Rust Series (#35) - Weak References & Breaking Reference Cycles

What will I learn

You will learn how a reference cycle causes Rc and Arc to leak memory, even in safe Rust;
what a Weak<T> reference is, and how it points at an allocation without owning it;
how Rc::downgrade and Weak::upgrade convert between the strong and weak worlds;
how to model a parent-child tree where children are owned strongly and back-pointers are weak;
how strong_count and weak_count let you confirm, with your own eyes, that you have no leak.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Rust toolchain (via rustup, from rustup.rs);
The previous thirty-four episodes, especially Rc internals (episode 33), interior mutability (episode 32), and Arc (episode 34);
The ambition to learn systems programming from the ground up.

Difficulty

Beginner

Curriculum (of the `Learn Rust Series`):

Learn Rust Series (#35) - Weak References & Breaking Reference Cycles

Twice now I have closed on the same loose end. In episode 33 we pried Rc open and saw that every reference-counted allocation carries two counts, a strong one and a weak one, and I told you the weak count existed for a reason we would get to later. In episode 34 we made the whole thing thread-safe with Arc, and again I signed off on the promise of a way to "point at a value without keeping it alive". Today we finally cash both promises in.

The problem the weak count solves is the one blind spot of reference counting: the cycle. If two Rcs point at each other, each keeps the other's strong count above zero forever, so neither is ever freed. You have leaked memory, in safe Rust, with no unsafe block and no raw pointer anywhere in sight. Rust does not prevent this at compile time, and it is important to understand why -- a leak is a logic error, not a memory-safety one. Nothing is corrupted, nothing dangles, no rule of ownership is broken; the memory is simply never reclaimed. What Rust gives you instead is the tool to design the cycle away: the weak reference, Weak<T>. But first, as always, let me clear last episode's homework ;-)

Solutions to Episode 34 Exercises

Episode 34 was Arc, thread-safe reference counting. There were three exercises, and here is full runnable code for each.

Exercise 1 asked you to share an Arc<Vec<i32>> across four threads that each print the sum of the vector, then, after joining every thread, confirm that Arc::strong_count has returned to one:

use std::sync::Arc;
use std::thread;

fn main() {
    let data = Arc::new(vec![1, 2, 3, 4, 5]);
    let mut handles = Vec::new();

    for id in 0..4 {
        let d = Arc::clone(&data); // atomic increment, then moved into the thread
        handles.push(thread::spawn(move || {
            println!("thread {id} sum = {}", d.iter().sum::<i32>()); // 15
        }));
    }

    for h in handles {
        h.join().unwrap();
    }
    println!("owners left: {}", Arc::strong_count(&data)); // 1
}

The shape here is the one from episode 34 that recurs in almost every threaded program: clone the Arc outside the closure into a fresh binding, then move that binding in. Each of the four threads owns its own handle onto the one shared Vec, nothing is copied per thread, and once every thread has finished and its handle has dropped, the strong count falls all the way back to one.

Exercise 2 wanted an Arc<Mutex<Vec<u32>>> with several threads that each push their own thread id into the shared vector; after joining, print the collected ids and confirm the length matches the number of threads:

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let ids = Arc::new(Mutex::new(Vec::new()));
    let mut handles = Vec::new();

    for id in 0..5 {
        let shared = Arc::clone(&ids);
        handles.push(thread::spawn(move || {
            shared.lock().unwrap().push(id); // lock, push, guard unlocks at ;
        }));
    }

    for h in handles {
        h.join().unwrap();
    }

    let mut collected = ids.lock().unwrap().clone();
    collected.sort(); // threads finish in any order, so sort for a stable print
    println!("ids: {collected:?}");         // [0, 1, 2, 3, 4]
    println!("count: {}", collected.len()); // 5
}

Two layers doing two jobs, exactly as we drilled: the Arc gives shared ownership across the five threads, the Mutex gives safe mutation. Note the little .sort() before printing -- the threads run in whatever order the scheduler picks, so the ids land in the vector in a non-deterministic order, and sorting makes the output reproducible. The length, of course, is always five regardless of order.

Exercise 3 asked you to take a single-threaded Rc<RefCell<i32>> counter and convert it into an Arc<Mutex<i32>> that several threads each increment, noting how few lines actually had to change:

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    // single-threaded original was: Rc::new(RefCell::new(0))
    let counter = Arc::new(Mutex::new(0));
    let mut handles = Vec::new();

    for _ in 0..4 {
        let c = Arc::clone(&counter);      // was Rc::clone(&counter)
        handles.push(thread::spawn(move || {
            *c.lock().unwrap() += 1;       // was *c.borrow_mut() += 1
        }));
    }

    for h in handles {
        h.join().unwrap();
    }
    println!("{}", *counter.lock().unwrap()); // 4
}

This is the whole point episode 34 hammered: switching from the single-threaded world to the multi-threaded one is close to a find-and-replace. Rc becomes Arc, RefCell becomes Mutex, borrow_mut() becomes lock().unwrap(), and the structure of the program is otherwise untouched. And if you had tried instead to send the original Rc<RefCell<i32>> into thread::spawn, the compiler would have stopped you flat, because Rc is neither Send nor Sync. Right, homework cleared -- now let us break some cycles ;-)

The cycle problem, concretely

Picture a tree where each node owns its children with Rc, and each child also points back to its parent with another Rc. On paper that sounds harmless, even tidy: navigate down through the children, navigate up through the parent. But think about the counts. The parent holds a strong Rc to the child, so the child's strong count includes that. The child holds a strong Rc back to the parent, so the parent's strong count includes that. Now drop your outside handles to both. The parent's count does not reach zero, because the child still points at it. The child's count does not reach zero, because the parent still points at it. Two allocations, each keeping the other alive, and no way left in the program to reach either of them. That is a leak.

The rule of thumb worth burning into memory is this: in any ownership graph with references in both directions, only one direction should own. The other direction must not contribute to the strong count at all. And that non-owning, does-not-keep-alive kind of reference is precisely what Weak is.

Weak: a reference that does not own

A Weak<T> refers to an Rc's allocation without keeping the value alive. It touches only the separate weak count, never the strong count, so it can never be the reason a value stays around, and therefore it can never be part of a cycle that leaks. You create one by downgrading an existing Rc with Rc::downgrade, and because the value it points at might already have been freed, you cannot just deref a Weak -- you have to upgrade it first, which hands you back an Option<Rc<T>>:

use std::rc::Rc;

fn main() {
    let strong = Rc::new(42);
    let weak = Rc::downgrade(&strong); // a non-owning handle onto the same allocation

    // The value is still alive, so upgrade succeeds and gives us a real Rc.
    println!("{:?}", weak.upgrade().map(|rc| *rc)); // Some(42)

    drop(strong); // the last strong owner is gone, so the value is freed now

    // The value is gone, so upgrade safely reports None. No dangling, no crash.
    println!("{:?}", weak.upgrade().map(|rc| *rc)); // None
}

This is the whole safety guarantee in one example: a Weak can never dangle. The instant the strong count hits zero the value is dropped, and from that point on every Weak pointing at it upgrades to None. You are not handed a pointer into freed memory and asked to be careful; you are handed an Option, and the None case is the compiler forcing you to acknowledge that the thing may be gone. That is a very different, and much safer, contract than the raw back-pointers you would reach for in C.

Two counts, watched side by side

Because weak handles live in their own separate count, you can inspect both at once with Rc::strong_count and Rc::weak_count and watch how they move independently:

use std::rc::Rc;

fn main() {
    let a = Rc::new(5);
    println!("strong {} weak {}", Rc::strong_count(&a), Rc::weak_count(&a)); // strong 1 weak 0

    let _w1 = Rc::downgrade(&a);
    let _w2 = Rc::downgrade(&a);
    // Downgrading did NOT touch the strong count -- only the weak one climbed.
    println!("strong {} weak {}", Rc::strong_count(&a), Rc::weak_count(&a)); // strong 1 weak 2
}

The strong count stays at one the whole time, because a is still the only owner; the weak count climbs to two as we create the two weak handles. And here is the key consequence: since weak handles do not affect the strong count, the value is freed the moment a drops, regardless of how many Weaks are still hanging around. Those surviving weak handles are not left dangling -- they simply start upgrading to None. The allocation itself sticks around in a tiny "tombstone" state until the last weak handle is also gone (that is what the weak count is really tracking), but your T, the actual data, is dropped and its memory reclaimed as soon as the strong count reaches zero.

Seeing a cycle leak with your own eyes

Abstract talk of "the count never reaches zero" is easy to nod along to and hard to truly believe. So let us make it concrete with a Drop implementation (episode 20), which announces the exact instant a node is freed. If the destructors never fire, we know the memory leaked:

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    other: RefCell<Option<Rc<Node>>>,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("dropping a node");
    }
}

fn main() {
    let a = Rc::new(Node { other: RefCell::new(None) });
    let b = Rc::new(Node { other: RefCell::new(None) });

    // Link them into a strong cycle: a points at b, b points back at a.
    *a.other.borrow_mut() = Some(Rc::clone(&b));
    *b.other.borrow_mut() = Some(Rc::clone(&a));

    println!("a strong = {}", Rc::strong_count(&a)); // 2
    println!("b strong = {}", Rc::strong_count(&b)); // 2

    // main ends here. The a and b bindings drop, taking each count from 2 to 1
    // -- but NEVER to 0, because each node still holds an Rc to the other.
    // Neither "dropping a node" line ever prints. Both nodes are LEAKED.
}

Run it, and you will notice something unsettling: the dropping a node message never appears. Not once. The two nodes hold Rcs to each other, so when main ends and the a and b bindings drop, each count falls from two only to one, and the destructors never run. This compiles cleanly, runs without a single warning, and quietly leaks -- the exact failure mode reference counting cannot catch on its own. As we noted back in episode 33, CPython has this identical blind spot, which is why it bolts a whole separate cyclic garbage collector on top. Rust makes a different bet: it hands you Weak and asks you to design the cycle out.

The fix: strong down, weak up

Here is that design. In a parent-child tree, ownership flows down: a parent owns its children, so those pointers are strong Rcs. The back-pointer flows up: a child refers to its parent, but does not own it, so that pointer is a Weak. With the up-direction weakened, no cycle of strong handles can form, and everything frees cleanly:

use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,      // weak: a child does NOT own its parent
    children: RefCell<Vec<Rc<Node>>>, // strong: a parent DOES own its children
}

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()), // starts with no parent
        children: RefCell::new(vec![]),
    });

    let branch = Rc::new(Node {
        value: 5,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![Rc::clone(&leaf)]), // branch owns leaf
    });

    // Give leaf a weak pointer up to its parent.
    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

    // Navigating UP requires an upgrade, because the parent might be gone.
    if let Some(parent) = leaf.parent.borrow().upgrade() {
        println!("leaf's parent value: {}", parent.value); // 5
    }

    println!("branch strong = {}, weak = {}",
        Rc::strong_count(&branch), // 1: only the `branch` binding owns it
        Rc::weak_count(&branch));  // 1: leaf's weak parent pointer
}

Look carefully at the counts at the end. branch has a strong count of one -- only the branch binding owns it -- and a weak count of one, from leaf's parent pointer. That weak pointer does not prop the strong count up, so when branch goes out of scope its strong count reaches zero and it is properly freed. Compare that with the leaking version above, where the back-pointer was a strong Rc and the count got stuck at one forever. One word changed -- Rc to Weak on the up-direction -- and the leak is gone.

Navigating down needs no upgrade

Because children are owned strongly, walking down the tree is just ordinary Rc access -- no upgrade, no Option to unwrap. A method that lists a node's children's values is completely straightforward:

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>>,
}

impl Node {
    fn children_values(&self) -> Vec<i32> {
        self.children.borrow().iter().map(|c| c.value).collect()
    }
}

fn main() {
    let leaf = Rc::new(Node { value: 3, children: RefCell::new(vec![]) });
    let root = Rc::new(Node {
        value: 1,
        children: RefCell::new(vec![Rc::clone(&leaf), Rc::new(Node { value: 2, children: RefCell::new(vec![]) })]),
    });
    println!("{:?}", root.children_values()); // [3, 2]
}

This asymmetry is the whole trick, and it is worth stating plainly: the owning direction is cheap and direct to follow, the non-owning direction costs you an upgrade and an Option. That extra step going up is not friction for its own sake -- it is the type system reminding you, at every single access, that the parent might already have been dropped, and making you handle that possibility. In stead of hoping a back-pointer is still valid, you are forced to check.

An empty Weak, and Arc's weak twin

Notice Weak::new() in the tree above. It builds a weak handle that points at nothing at all -- a perfectly valid "no parent yet" placeholder that simply upgrades to None until you assign a real downgraded pointer into it:

use std::rc::Weak;

fn main() {
    let orphan: Weak<i32> = Weak::new();
    // Points at no allocation whatsoever, so it always upgrades to None.
    println!("{:?}", orphan.upgrade()); // None
}

And everything in this episode applies, unchanged in spirit, to the thread-safe world. Arc has its own std::sync::Weak, produced by Arc::downgrade, with exactly the same upgrade -> Option<Arc<T>> contract. If you build a shared graph across threads and it needs back-pointers, you weaken the up-direction with an Arc-flavoured Weak in precisely the same way:

use std::sync::{Arc, Weak};

fn main() {
    let strong = Arc::new(String::from("shared across threads"));
    let weak: Weak<String> = Arc::downgrade(&strong);

    println!("{:?}", weak.upgrade().map(|a| a.len())); // Some(21)
    drop(strong);
    println!("{:?}", weak.upgrade().map(|a| a.len())); // None
}

Same story, atomic counts. The design rule does not change one bit between Rc and Arc -- only the thread-safety of the counting underneath does, exactly as episode 34 laid out.

The rule for graphs

Let me distill it, because this is the takeaway you should carry out of the episode. Whenever you build a data structure with references pointing in more than one direction, decide which direction expresses ownership and make that one Rc (or Arc). Make every other direction Weak. Parents own children; children refer back weakly. It generalises far beyond trees: a doubly-linked list where each node points both forward and back, an observer that points at the subject it watches, a cache entry that refers to the cache holding it -- in each of these, you pick the single owning direction and weaken the rest.

And the diagnostic is just as mechanical. If you ever notice memory that should have been freed sticking around -- a Drop that never prints, a count that will not fall to zero -- a strong cycle is the first thing to suspect. The fix is almost always to find one leg of the loop and convert it to Weak. Having said that, do not sprinkle Weak everywhere out of paranoia; most structures have no cycles at all, and a plain Rc tree with no back-pointers cannot leak in the first place. Weak is the specific antidote to the specific disease of the ownership loop.

How Python sees this

Since quite some of you arrived here from the Learn Python Series, a glance sideways is illuminating, because Python fights the very same battle and solves it differently. As we saw in episode 33, CPython reference-counts every object, and that means CPython inherits the identical cycle problem -- two objects referring to each other never see their counts fall to zero:

class Node:
    def __init__(self):
        self.other = None

a = Node()
b = Node()
a.other = b
b.other = a   # a strong cycle, exactly like the Rc version above

# Deleting the names does NOT immediately free the objects: their refcounts
# are still 1 each, because they point at each other.
del a
del b
# CPython's separate cyclic garbage collector eventually sweeps these up.

Python's answer is to run a background cyclic garbage collector that periodically hunts down these unreachable islands and reclaims them. It works, but it costs you: unpredictable pauses, extra runtime machinery, and a weakref module for the cases where you want to opt out of keeping something alive. Rust makes the opposite bargain. There is no background collector scanning your heap; instead you express the non-owning relationship directly in the types with Weak, the cycle never forms, and the memory frees deterministically the instant the last strong owner drops. You do a little more thinking up front about who owns whom; you get no surprise pauses and no hidden collector. I argue that, for systems code, that is a very reasonable trade.

What did we actually learn?

A cycle of strong Rcs (or Arcs) leaks: each handle keeps the other's strong count above zero, so no destructor ever runs. This compiles and runs cleanly -- a leak is a logic error, not a memory-safety one, so the compiler does not stop it.
Weak<T> points at an allocation without owning it. It touches only the weak count, never the strong count, so it can never keep a value alive and can never be part of a leaking cycle.
You create a Weak with Rc::downgrade and, because the value may already be gone, you must upgrade it, which returns an Option<Rc<T>> -- None once the value has been freed. A Weak can therefore never dangle.
Rc::strong_count and Rc::weak_count let you watch the two counts move independently and confirm you have no leak.
The design rule: in any graph with references in both directions, make the owning direction Rc/Arc and every other direction Weak. Parents own children strongly; children point back weakly.
Everything carries over to threads: Arc has its own Weak via Arc::downgrade, with the identical upgrade contract.
Where Python leans on a background cyclic garbage collector, Rust has you express non-ownership directly with Weak, so cycles free deterministically with no runtime collector.

Exercises

Three exercises, from gentle to chewier. Type them yourself before the next episode -- that is where the understanding sticks.

Build a two-node structure where each node holds a RefCell<Option<Rc<Node>>> and link them into a strong cycle. Give Node a Drop impl that prints, run it, and confirm the destructors never fire. Then reason, in a comment, about exactly why each strong count gets stuck at one.
Rewrite that structure so one direction is a Weak in stead of an Rc. Add the same Drop impl and confirm that now both dropping... lines DO print, and that strong_count on the weakened node reads one, not two.
Extend the parent-child tree with a parent_value(&self) -> Option<i32> method that upgrades the weak parent pointer and returns the parent's value, or None at the root. Verify it returns Some(5) for a leaf whose parent has value 5, and None for the root itself.