6 min udev

On Arc

Reasoning about why Arc exists, and understanding how it works

rust memory concurrency async atomics

Introduction

Lately I've been picking apart the tools I use every day, just to see what's underneath. The old way had a cycle: googling, scrolling, writing, then stumbling into some rabbit hole that took you deeper than you planned. An LLM gives you the answer in a couple of keystrokes: what you need, but not what you want. Reading how a thing is really built is the part I'd been missing, where you get to appreciate someone's thinking and craft, and actually feel like you're standing on the shoulders of giants.

This weekend I picked Arc. Atomic reference counting has always been a wonderful, omnipresent smart pointer in my 5 years of writing Rust code. This time I truly wanted to understand how it works internally. To be honest, I have been going through Mara Bos's book on locks and atomics in Rust. I'll be taking some code snippets from Chapter 6 of this book as I feel it gives really good, digestible code for understanding this smart pointer.

Why not use Rc?

Nobody would use Rc in a multithreaded program. The Rust compiler won't let them. But why?

The one-line answer: Because integers lie to you when two threads try mutating them at once. Reliable systems hate liars.

Long(ish) answer: The integer that tracks the reference count can forget about references created concurrently on other threads. That's disastrous, as once the count reaches zero, the allocator reclaims the memory and a holder of a forgotten reference can run into use-after-free scenarios. This can lead to a segfault or silent corruption, exactly the class of bug Rust exists to prevent.

Memory isn't one shared blackboard

Memory feels like a shared blackboard. In a single-threaded program that's mostly fine: one person reads and writes, and the causality of events is easy to follow. Things turn messy the moment you add another person.

What you actually discover is that the blackboard isn't where the data lives during the actual work. Each person has a small private scratchpad, and that's where the value gets copied to, worked on, and eventually written back. The blackboard is DRAM. The private scratchpad is each core's L1 cache (L2 is usually private too; L3 is a shared middle layer that sits between the L1s and DRAM). The reason this matters: when Core 1 modifies a value in its L1, Core 2 doesn't see the change instantly. Modern CPUs run a cache coherence protocol that eventually synchronizes the L1s, but "eventually" is doing a lot of work in that sentence. And crucially, if two cores each do a read → modify → write on the same value at the same time, nothing in the ordinary machine stops both of them from reading the same old value, computing the same new value, and clobbering each other's update.

That's the crack Rc falls through.

The Arc of Arc

Now that we know why Rc is not the right pointer for multithreaded programs, we can move on to how to fill the gaps using atomics. The use of atomics is what adds the A in Arc.

Abbreviated from Atomically Reference Counted, it solves the core problem of multiple cores updating the same shared memory at the same time, causing loss of intermediate operations. This is what an implementation of Arc would look like:

struct ArcData<T> {
    ref_count: AtomicUsize,
    data: T,
}

use std::ptr::NonNull;

pub struct Arc<T> {
    ptr: NonNull<ArcData<T>>,
}

NonNull here is just a pointer which guarantees that the thing it points to is not null. We don't use mut T or const T because of:

1. Covariance (without giving up write ergonomics, which is why NonNull over *const T)

2. Niche optimization for Option<Arc<T>>, where its size will be the same as Arc<T>

3. The non-null invariant encoded in the type system.

ref_count is our internal counter which keeps a record of the references generated. Since we are the custodian of T, we will need to know when the memory needs to be freed back to the allocator. While creating references increases the reference counter, dropping the references decreases it.

Two small helpers are implied by the snippets below. Constructing an Arc boxes up an ArcData with ref_count initialised to 1 and stashes the pointer:

impl<T> Arc<T> {
    pub fn new(data: T) -> Arc<T> {
        Arc {
            ptr: NonNull::from(Box::leak(Box::new(ArcData {
                ref_count: AtomicUsize::new(1),
                data,
            }))),
        }
    }

    fn data(&self) -> &ArcData<T> {
        unsafe { self.ptr.as_ref() }
    }
}

data() is just a convenience that dereferences ptr to reach the ArcData, and we'll lean on it in both Clone and Drop.

We need to implement Send and Sync for Arc<T> so that the compiler allows using Arc in multithreaded programs. Implementing them is easy, just use unsafe here:

unsafe impl<T: Send + Sync> Send for Arc<T> {}
unsafe impl<T: Send + Sync> Sync for Arc<T> {}

Now, using unsafe here should not be without reason, as we are asking the compiler to trust the code so that it can safely treat it as Send and Sync. We do that by using atomics in the Clone and Drop implementations.

Trust me, compiler…

By that, we mean we make sure that there are no use-after-free or double-free issues with our Arc implementation.

The ordering of clone operations does not matter because there are no other atomic operations required to happen strictly before or after it. Hence we can use Relaxed Ordering here in our clone operation.

impl<T> Clone for Arc<T> {
    fn clone(&self) -> Self {
        self.data()
            .ref_count
            .fetch_add(1, std::sync::atomic::Ordering::Relaxed);
        Arc { ptr: self.ptr }
    }
}

However, the drop operation has a catch. When the ref_count drops from 1 to 0 is when we actually free the memory. Up until that final free operation, we need to make sure that no references are active when we free the memory. We do this by decrementing the counter with Release ordering and then, on the final drop, issuing an Acquire fence before freeing. 

impl<T> Drop for Arc<T> {
    fn drop(&mut self) {
        if self
            .data()
            .ref_count
            .fetch_sub(1, std::sync::atomic::Ordering::Release)
            == 1
        {
            fence(std::sync::atomic::Ordering::Acquire);
            unsafe { drop(Box::from_raw(self.ptr.as_ptr())) }
        }
    }
}

The drop is an interesting implementation because of two things:

There are more hidden secrets and fascinating mechanisms if we dive in deeper, but that is out of the scope of this blog. I may do a separate write-up for those as I learn more about them and keep improving my understanding of atomics. For now, this covers all the noteworthy things that I think folks should know about Arc, which allows us to simply clone things safely and reduces our cognitive load.

← All posts · About · RSS