Cache Coherence and MESI

Learning objective

Explain why a write to a cache line requires exclusive ownership of that line, distinguish cache coherence from memory consistency and memory ordering, and follow a line's state transitions across two cores through read misses, write misses, read-for-ownership, invalidation, cache-to-cache transfer, write-back, and eviction — while clearly separating this conceptual MESI teaching model from what any specific real processor implements.

Prerequisites

• A basic idea of what a CPU cache and a cache line are. No prior knowledge of coherence protocols is assumed — this lab builds it from scratch. (If you've done the False sharing lab, this explains the mechanism beneath the symptom shown there — but that lab is not required first.)

Theory

Coherence vs. consistency vs. memory ordering

Cache coherence answers: for a single memory location, do all cores eventually agree on its value, and is there a well-defined order of writes to that one location that every core observes consistently? Coherence is a per-location guarantee, enforced by hardware protocols like MESI.

Memory consistency (the memory model) answers a much broader question: across multiple different memory locations, what orderings between operations is a program allowed to observe? Two coherent caches can still permit surprising reorderings across different addresses unless the consistency model forbids it.

Memory ordering (fences, volatile, Ordering::Acquire/Release, happens-before) is the language- and hardware-level mechanism used to constrain what a consistency model otherwise allows.

The MESI states

MESI names four states a cache line can be in, from any one core's point of view:

The state that makes MESI more than a toy: Exclusive. A line fetched by a read, when no other core holds any copy, becomes Exclusive rather than Shared — so a later write to that same line by the same core silently upgrades Exclusive → Modified with no bus traffic at all, because no other cache needs to be told anything. Without an Exclusive state, that write would issue an invalidation broadcast even though nothing else was sharing the line.

Transitions the interactive model demonstrates

• Read miss, no sharers — fetches from memory, takes the line Exclusive.
• Read miss, another core holds it clean — a cache-to-cache transfer supplies the data; both end up Shared, downgrading a lone Exclusive holder.
• Read miss, another core holds it Modified — the dirty holder transfers its value and writes it back to memory (which was stale); both end up Shared.
• Write miss (read-for-ownership) — every other copy must be invalidated before the requester becomes sole Modified owner; a Modified holder is transferred and written back first.
• Write hit, Exclusive → Modified — silent local upgrade, no bus transaction.
• Eviction — a Modified line must be written back first; an Exclusive or Shared line is simply dropped.

Caveats: a teaching model, not a universal contract

MESIF (some Intel processors) adds a Forward state so only one Shared holder answers a snoop. MOESI (some AMD processors) adds an Owned state, letting a Modified line be shared without an immediate write-back. Directory-based coherence replaces broadcast snooping with a directory tracking sharers, used because broadcast snooping stops scaling past a modest core/socket count — common on large multi-socket servers. ARM and Apple Silicon: ARM's architecture reference does not mandate one specific coherence protocol, and Apple has not published the exact protocol its silicon uses — this lab does not claim to model either.

Java and Rust

public class SharedWriterExample {
    // Two threads both write this counter, from different cores — the JVM
    // guarantees atomicity and visibility, but says nothing about, and does
    // not let you observe, which coherence protocol state the line is in.
    private final AtomicLong counter = new AtomicLong();

    public void incrementFrom(int iterations) {
        for (int i = 0; i < iterations; i++) counter.incrementAndGet();
    }

    public long value() { return counter.get(); }
}

public class SingleOwnerExample {
    // No synchronization needed: exactly one thread ever reads or writes
    // this field for the object's whole lifetime. In coherence terms, that
    // thread's core can hold this line Exclusive/Modified indefinitely and
    // never has to respond to another core's invalidation.
    private long total;

    public void addFrom(int iterations) {
        for (int i = 0; i < iterations; i++) total += i;
    }

    public long total() { return total; }
}

use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Arc;

/// Two threads both call `increment` on the same instance, from different
/// cores — `Relaxed` is sufficient here since only the counter's own
/// atomicity matters, not ordering relative to other memory operations.
pub struct SharedWriter {
    counter: AtomicU64,
}

impl SharedWriter {
    pub fn new() -> Self { Self { counter: AtomicU64::new(0) } }
    pub fn increment(&self) { self.counter.fetch_add(1, Ordering::Relaxed); }
    pub fn value(&self) -> u64 { self.counter.load(Ordering::Relaxed) }
}

/// No atomics, no synchronization: exactly one thread ever touches `total`
/// for the value's whole lifetime, so there is no other core to invalidate
/// this line — the software analogue of an Exclusive/Modified single owner.
pub struct SingleOwner {
    total: u64,
}

impl SingleOwner {
    pub fn new() -> Self { Self { total: 0 } }
    pub fn add_from(&mut self, iterations: u64) {
        for i in 0..iterations { self.total += i; }
    }
    pub fn total(&self) -> u64 { self.total }
}

Diagnostic methodology: perf c2c

perf c2c (Linux perf's cache-to-cache module) samples hardware performance-monitoring-unit events tagged with the physical cache line address involved in a load, and groups them by which cores took cross-core "HITM" (hit-modified) responses — i.e. cache-to-cache transfers of a dirty line, exactly the transition the "competing writers" and "reader then writer" scenarios above model. It requires:

• A Linux kernel and CPU with the relevant PMU events available (`perf c2c record`/`perf c2c report`) — this is Linux-specific tooling; there is no equivalent invocation on macOS.
• Sufficient privileges to use hardware performance counters (commonly CAP_PERFMON/CAP_SYS_ADMIN, or a permissive /proc/sys/kernel/perf_event_paranoid).
• A workload that actually contends — running perf c2c against a single-threaded program produces nothing interesting to report, by construction.

# Record cache-to-cache events for a running workload
perf c2c record -- ./your-contended-workload

# Summarize which cache lines saw the most HITM (cache-to-cache) traffic
perf c2c report --stdio

Caveats: exact event availability and column meaning vary by microarchitecture and kernel version; virtualized environments frequently restrict or disable the underlying PMU events entirely; and perf c2c's output identifies contended cache lines and the cores/threads touching them, not MESI state names — the mapping from "HITM" back to "this was a Modified→Shared transition" is an interpretation this lab teaches, not something the tool states directly.

Common mistakes

• Treating MESI as the coherence protocol every CPU implements — it is a teaching model; real hardware ships MESIF, MOESI, or directory-based coherence.
• Assuming coherence gives you memory ordering for free — coherence guarantees agreement on one location's value, not the order in which writes to different locations become visible.
• Assuming Apple Silicon, or any specific chip, is "just MESI" — vendors rarely publish their exact protocol.
• Confusing invalidation with write-back — invalidation discards a stale copy; write-back flushes a dirty value to memory. A single transition can require both, or just one.
• Reading perf c2c output as if it named MESI states directly — it reports contended cache lines and cross-core HITM events, which this lab's theory maps to MESI transitions, but the tool itself does not use MESI terminology.

Investigation task

Using the Java or Rust project in code/, and a Linux machine with perf available:

1. Run two threads concurrently calling the shared-writer example's increment method on the same instance, and separately run the single-owner example on one thread only.
2. Record perf c2c record/perf c2c report output for the shared-writer run and look for HITM (cache-to-cache, dirty-line) events on the counter's address.
3. Re-run perf c2c against the single-owner example and confirm it reports little or no HITM traffic for that field — there is only one core ever touching it.
4. Change the shared-writer benchmark to pin both threads to the same physical core (if your OS exposes CPU affinity) instead of different cores, and predict — then confirm — whether HITM events for that line disappear even though both threads still write it concurrently.
5. Write down your CPU model, core topology, and what you observed, and explain any difference from the mechanism described in "Theory" above.

Accessibility notes

• The interactive model is fully keyboard operable: the scenario selector and the Java/Rust code tabs are roving-tabindex tablists (arrow keys, Home/End); every read/write/evict/step/reset control is a native <button>.
• Every state change is announced to screen readers via an aria-live="polite" region, in addition to the visible state badges and the state inspector table — state is never colour-only.
• The coherence-bus pulse is the only animation on this page; it plays once per action and is fully collapsed under prefers-reduced-motion: reduce (this page has no auto-playing or looping animation to separately gate on that preference).
• With JavaScript disabled, this page's theory, Java and Rust code, diagnostic methodology, trade-offs and sources remain fully readable — only the interactive model and the graded quiz require script.

Review questions

Self-check before or after the graded quiz below:

1. Why does a write to an Exclusive line cost no bus traffic, while a write to a Shared line does?
2. Give a concrete example of something cache coherence guarantees, and something it does not (that memory ordering separately provides).
3. Why does reading a line held Modified by another core force both a write-back and a transfer, rather than just one or the other?
4. Name one thing a real processor's coherence protocol might do differently from this lab's four-state model.

Sources

• A Primer on Memory Consistency and Cache Coherence — Sorin, Hill, Wood, Morgan & Claypool, 2011.
• Computer Organization and Design: The Hardware/Software Interface — Patterson & Hennessy.
• Intel 64 and IA-32 Architectures Software Developer's Manual, Vol. 3A §11 (Memory Cache Control) — intel.com/sdm
• AMD64 Architecture Programmer's Manual, Vol. 2 — Cache Coherency — amd.com/support/tech-docs
• Arm Architecture Reference Manual — memory ordering and coherency — developer.arm.com/documentation/ddi0487
• perf-c2c(1) — Linux manual page — man7.org/linux/man-pages/man1/perf-c2c.1.html
• Java Concurrency in Practice — Goetz et al., Addison-Wesley, 2006.
• The Rust Reference — Atomics and concurrency — doc.rust-lang.org/std/sync/atomic