Multi-Core Cache Coherency: The Invisible Lock You Never Wrote

Sources this series builds on: Chili's (ChiliTomatoNoodle) multithreading
playlist,
CMU 15-213 (Computer Systems: A Programmer's Perspective), various CppCon talks,
and LLMs for restructuring and sanity-checking. Everything here is my own code,
compiled and run — not just transcribed.

Recap — and the question this article finally answers

Parts 3 through 5 built up a single-core picture: bytes and addresses, why
caches exist, and cache lines as fixed 64-byte aligned chunks. This article
introduces the piece that was missing — what happens when more than one
core wants the same memory at the same time — and it's the direct,
mechanical answer to the question this series has been sitting on since
Part 1: why did the mutex-protected version cost 13.2 seconds, over 4x
slower than not threading at all?

The new problem: private caches, shared memory

Registers, L1, and L2 are private per core. Only L3 and RAM are shared
across the whole chip (Part 4). That means the same 64-byte cache line can
end up copied into more than one core's private cache at the same time.

If nothing handled this, one core could write a value and another core
could read the same location moments later and get something already out
of date — not because of a bug in your code, purely because of where the
data happened to be cached. Hardware solves this fully automatically, with
no code from you required, via a coherency protocol.

The four states every cached line is tagged with (MESI)

The most common protocol family is called MESI, named after the four
states a cached line can be in on any given core:

• Modified (M) — only this core has it, and it's dirty (differs from memory). Free to read or write. Nobody else has a copy.
• Exclusive (E) — only this core has it, and it's clean (matches memory). Free to read; writing it silently flips it to Modified with zero bus traffic, since nobody else needs telling.
• Shared (S) — this core and at least one other core have clean copies. Free to read. Cannot write without first evicting everyone else's copy — this is the expensive transition.
• Invalid (I) — this core doesn't have a usable copy. The next access is a miss.

Every private cache runs this state machine independently, watching every
other core's traffic to know when to react. You don't configure it or see
it — it's just always running.

What actually crosses the wires

The state diagram shows the outcome. What physically happens on the
interconnect between cores is a small set of message types — every cache
"snoops" (watches) this traffic to see if it needs to react:

Here's the exact sequence two cores fighting over one line generate, every
time ownership swings back and forth:

Every BusRdX round trip costs on the order of the L3/interconnect
latency — tens of cycles — even though the actual arithmetic underneath is
a single cycle. This ping-pong is what's actually being measured whenever
two cores contend for the same line — not the math.

A cost ladder — not every core-to-core interaction is equal

Two cores sharing a line can meet in several different ways, and they are
not all the same price. Cheapest to most expensive:

The bottom row — write, while the other core is sitting on a dirty
(Modified) copy — is the one that matters most for this series:

Once two threads are both actively writing the same line, every single
write from either side lands in exactly this scenario — because whichever
side wrote last leaves the line Modified, which is precisely the expensive
case for whoever writes next. This back-and-forth, repeating on every write,
is the physical mechanism behind Part 1's 13.2 seconds: 400 million
lock/write cycles, each one paying this full flush-and-invalidate round
trip whenever the line had bounced to the other core since the last write.

The key insight: invalidation happens per line, not per variable

The coherency protocol doesn't know or care that a line contains "your
variable A" and "my unrelated variable B." It only knows this line was
written to — so it invalidates the whole line for every other core
holding it, even if those cores only ever touch a completely different
variable that just happens to live in the same 64 bytes.

Two threads can have zero shared variables in their own program logic —
no mutex, no atomic, nothing that looks like synchronization in the code at
all — and still slow each other down, purely because the hardware treats a
write to any part of a line as a reason to invalidate the entire line. This
isn't hypothetical. It's exactly what's waiting in the next article.

Wait — doesn't this mean coherency already prevents races?

Worth closing a gap explicitly, because it's a natural question once you've
seen how much machinery MESI actually runs: if hardware keeps every core's
cache honest automatically, why did Part 1's cnt += x still race?

Because coherency is a per-transaction guarantee, and cnt += x is not
one transaction — it's three (Part 1: read, modify, write). MESI correctly
guarantees that each individual read or write sees a consistent value.
It says nothing about a sequence of them. Nothing in MESI stops Core B
from sneaking in its own read between Core A's read and Core A's write —
there's no rule saying "once a core reads a line intending to write it
back, nobody else may touch that line until it does." That gap is exactly
where a race condition lives.

Every individual bus transaction above was perfectly coherent — the line
moved Shared → Modified → Invalid → Modified exactly as MESI dictates.
Coherency did its job at every single step. The bug isn't in the protocol;
it's in the gap between load and store, a gap coherency was never designed
to close. This is exactly what the lock prefix fixes and coherency alone
doesn't: it extends exclusive ownership across the whole read-modify-write,
not just one step of it, so no other core's read can slip into that gap.

Glossary added this part

Takeaways

• Cache coherency is real, automatic, and enforced entirely in hardware via a state machine (commonly MESI) and a small set of bus messages — no code of yours configures or sees it directly.
• Not all core-to-core interactions cost the same. Writing while another core holds a dirty copy is the most expensive case there is — a full flush, invalidate, and transfer, every time — and it's exactly the case two threads land in on every write once they're actively contending for one line.
• Coherency and atomicity are different guarantees. Coherency keeps a single access honest; atomicity (the lock prefix) keeps a sequence of accesses honest. cnt += x needs both, and plain non-atomic code only ever gets the first one — which is exactly why Part 1's race happened despite coherency running the whole time.
• Invalidation happens per cache line, not per variable — two threads with zero shared variables in their own logic can still contend, purely from memory layout.