MESI Transitions and the Traffic an Invalidation Generates

Two cores reading and writing the same address need a rule for what each is allowed to see. Cache coherence supplies it with an invariant narrow enough to implement in hardware: for any address, all cores agree on the order of writes to it, and a read returns the most recent write in that order. The mechanism that maintains the invariant is a per-line state machine plus a set of transactions on a shared interconnect. MESI is the canonical form of that state machine, and its transitions explain most of what a multiprocessor program observes when it shares data.

Four states and what they license

Each cache line carries two bits of coherence state alongside the tag. The states describe what the local cache may do without asking anyone:

• Modified. The line is present, dirty, and this cache is the only one holding it. Memory’s copy is stale. The cache may read and write freely, but it must supply the line if another core requests it, and it must write it back when it evicts.
• Exclusive. The line is present and clean, and no other cache holds it. The cache may read freely, and it may write without a transaction because the write makes it Modified and no other copy needs invalidating.
• Shared. The line is present and clean, and at least one other cache may hold it. Reads are free. A write requires invalidating every other copy, so the cache must request ownership first.
• Invalid. The line is not usable. Any access misses.

Exclusive exists to make a common case cheap: a core that reads a line no one else has can write it immediately. A protocol without it must send an invalidation on every first write even when the line is private, which is why the four-state form replaced the three-state MSI form.

The distinction between Shared and Exclusive matters for the same reason in reverse. A read that finds the line in no other cache installs it as Exclusive; a read that finds it elsewhere installs it as Shared. Whether a read is exclusive is determined by the response to the read request, which means the request must ask the question — a read-exclusive transaction distinct from a plain read.

Transactions that move lines

The protocol’s transitions are driven by local accesses and by messages from the interconnect. In a snooping design, every cache observes every transaction and reacts if it holds the line. The transactions are few:

Transaction	Issued by	Effect on other caches
Read	Core load miss	A Modified holder downgrades and supplies data; Shared holders stay Shared
Read for ownership	Core store miss, or store to a Shared line	All holders invalidate; a Modified holder supplies data
Write-back	Eviction of a Modified line	None; the line is no longer held
Flush	Explicit cache maintenance	A Modified holder writes the line back and invalidates

The read-for-ownership path is where the cost lives. A store to a line in Shared must invalidate every other copy before the write becomes visible, because coherence requires all caches to agree on the order. The requester broadcasts, waits for acknowledgements from every sharer, then writes. The wait is one interconnect round trip plus the time for each sharer to process the invalidation, and it happens on the first write to any line that was shared. Subsequent writes hit in Modified and cost nothing, which is the same deferral that write-back caching relies on within a single core.

/* The local sequence a core performs on a store that misses or that finds
   the line Shared: acquire ownership, then write. The wait is a coherence
   round trip, not a memory latency. */
static void store_word(struct cache *c, unsigned long addr, unsigned long val)
{
    struct line *l = find_line(c, addr);

    if (!l || l->state == SHARED) {
        l = acquire_ownership(c, addr);   /* read-for-ownership if absent,
                                             upgrade if shared */
        /* acquire_ownership returns only after every other copy has been
           invalidated and acknowledged */
    } else if (l->state == INVALID) {
        l = fill_exclusive(c, addr);      /* absent, but nobody else has it */
    }
    l->state = MODIFIED;                  /* Exclusive becomes Modified locally */
    store_into(l, addr, val);
}

The two cases collapse into one because both require the line in Modified. The difference is that the Invalid case also needs the data, so the response carries 64 bytes; the Shared case already has the data and needs only permission, so a design may implement the upgrade as a separate transaction that transfers no data. The accounting still hurts when a line migrates: a shared line that one core writes and another then reads costs an ownership acquisition followed by a transfer of the dirty line from the new owner, plus the eventual write-back when that owner evicts it. Three transactions carry one line’s worth of data across the machine for one write and one read.

False sharing is a line-granularity artifact

Coherence operates on lines, not variables. Two independent variables that happen to occupy the same 64-byte line are one coherence object. If core A writes x and core B writes y, and x and y are adjacent in memory, each write invalidates the other’s copy. The line ping-pongs between the two caches, and every write pays the read-for-ownership latency even though neither core touches the other variable.

The traffic is entirely spurious but the cost is real. For a loop that increments a per-thread counter stored in an array of unsigned long, eight counters share a 64-byte line, and eight cores each writing their own counter serialise on that line. The loop’s throughput collapses to the rate of one coherence transfer per write, which can be two orders of magnitude below the rate of a local increment. The fix is padding: each counter occupies its own line, wasting 56 bytes per counter and removing the sharing. That is the right trade whenever the counters are written in a hot loop and there are few of them.

/* Padding a per-thread counter so each occupies its own cache line (C11). */
struct padded_counter {
    _Atomic unsigned long value;
    char pad[64 - sizeof(unsigned long)];
};

_Alignas(64) struct padded_counter counters[MAX_THREADS];

The alignment specifier is necessary as well as the padding: without it the array may start mid-line and its first element will still share with a neighbour. _Alignas(64) on the array makes every element start on a line boundary only because the element size is itself a multiple of 64 — which the padding guarantees — so the two parts of the fix depend on each other. The value of 64 is architecture-specific — x86-64 and most Arm cores use 64-byte lines, some use 128 — and code that must be portable cannot assume it, which is why some platforms provide a named constant or a macro for the destructive interference size.

False sharing is invisible in a profile that counts instructions or cache misses per core. Each core sees a modest number of coherence misses, and the aggregate looks unremarkable. What reveals it is a count of invalidation transactions or a stall reason attributed to coherence, and the fix requires knowing the layout, which means looking at the struct definition rather than at the algorithm.

Directory protocols and the scaling limit

Snooping works because every cache sees every transaction, which requires a shared bus or a broadcast-capable interconnect. Both stop scaling at a few tens of cores: a broadcast to 64 caches per miss is 64 messages, and the bus bandwidth is shared among all of them. Large machines therefore use directory coherence, where a per-line or per-block directory records which caches may hold the line, and a request is sent only to those.

The directory trades bandwidth for latency and storage. It is also the role an inclusive last-level cache plays when it holds every private line and can answer presence from its own tags. A full directory with one presence bit per cache per line costs, for 64 caches and 64-byte lines, 8 bytes of directory per 64 bytes of data — a 12.5 percent overhead on the whole memory. Sparse directories reduce that by tracking a limited number of sharers per block and falling back to broadcast when the list overflows, which reintroduces the scalability problem for exactly the lines that are most widely shared. The compromise in real systems is a directory at the last-level cache, where the line’s home is, with a coarse vector per block and a broadcast for the overflow case.

The failure mode of a directory is the same as that of snooping, displaced: a widely shared read-only line causes every sharer to be recorded, and a write to it generates a flood of invalidations. A read-mostly line that is written once per epoch is the worst case for any protocol, because the write must collect acknowledgements from all sharers and the read must re-establish them. This is why read-mostly data structures in large machines are either replicated per core or protected by a lock that batches the writes, and why the memory model’s release and acquire operations exist to let software express a batching that the hardware cannot infer.

Both protocols share an assumption that is worth stating: coherence concerns a single address, and the memory consistency model concerns the order of accesses to different addresses. A coherent machine can still present a program with a reordering that violates sequential consistency, which is why fences are needed even when every line is coherent. Coherence says nothing about the ordering a program may rely on, and a protocol that gets every state transition right can still leave a programmer with a machine whose observed order is not the program order.